Every subcubic multigraph is $(1,2^7)$-packing edge-colorable

Abstract

For a non-decreasing sequence $S=(s_1,\dots ,s_k)$ of positive integers, an $S$-packing edge-coloring of a graph $G$ is a decomposition of edges of $G$ into disjoint sets $E_1,\dots ,E_k$ such that for each $1\le i\le k$ the distance between any two distinct edges $e_1,e_2\in E_i$ is at least $s_i+1$. The notion of $S$-packing edge-coloring was first generalized by Gastineau and Togni from its vertex counterpart. They showed that there are subcubic graphs that are not $(1,2,2,2,2,2,2)$-packing (abbreviated to $(1,2^6)$-packing) edge-colorable and asked the question whether every subcubic graph is $(1,2^7)$-packing edge-colorable. Very recently, Hocquard, Lajou, and Lužar showed that every subcubic graph is $(1,2^8)$-packing edge-colorable and every $3$-edge colorable subcubic graph is $(1,2^7)$-packing edge-colorable. Furthermore, they also conjectured that every subcubic graph is $(1,2^7)$-packing edge-colorable. In this paper, we confirm the conjecture of Hocquard, Lajou, and Lužar, and extend it to multigraphs.

24 pages, 4 figures