Theoretical analysis demonstrates (1^2,2^4)-packing edge-colorability in connected subcubic graphs with over 70 vertices, highlighting the sharpness of conjectured graph coloring bounds.
An induced matching in a graph G is a matching such that its end vertices also induce a matching. A (1^, 2ᵏ)-packing edge-coloring of a graph G is a partition of its edge set into disjoint unions of matchings and k induced matchings. Gastineau and Togni (2019), as well as Hocquard, Lajou, and Lu{z}ar (2022), have conjectured that every subcubic graph is (1²,2⁴)-packing edge-colorable. In this paper, we confirm that their conjecture is true (for connected subcubic graphs with more than $70$ vertices). Our result is sharp due to the existence of subcubic graphs that are not (1²,2³)-packing edge-colorable.
No takes yet. Share an insight, caveat, or question.
Liu et al. (2024) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: