On the (1²,2⁴)-packing edge-coloring of subcubic graphs

2024/02/28 by Xujun Liu, Liu, Xujun, Gexin Yu +1
Computer Science · Engineering · #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Interconnection Networks and Systems #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.2402.18353

openalex publication_date 2024/02/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

An induced matching in a graph G is a matching such that its end vertices also induce a matching. A (1^ℓ, 2^k)-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ž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.

Related

• Every subcubic multigraph is (1,2⁷)-packing edge-colorable
• Partition subcubic planar graphs into independent sets
• Packing edge-colorings of subcubic outerplanar graphs
• Every subcubic graph is packing (1,1,2,2,3)-colorable
• Advances on the Packing Coloring Conjectures of Subcubic Graphs