TY - JOUR
T1 - Every subcubic multigraph is (1,27)-packing edge-colorable
AU - Liu, Xujun
AU - Santana, Michael
AU - Short, Taylor
N1 - Funding Information:
We thank two anonymous reviewers for their valuable comments. The research of X. Liu was supported by the Natural Science Foundation of the Jiangsu Higher Education Institutions of China 20220120 and the Research Development Fund RDF‐21‐02‐066 of Xi'an Jiaotong‐Liverpool University. The research of M. Santana was supported by the AMS‐Simons Travel Grant.
Publisher Copyright:
© 2023 Wiley Periodicals LLC.
PY - 2023/12
Y1 - 2023/12
N2 - For a nondecreasing sequence (Formula presented.) of positive integers, an (Formula presented.) -packing edge-coloring of a graph (Formula presented.) is a decomposition of edges of (Formula presented.) into disjoint sets (Formula presented.) such that for each (Formula presented.) the distance between any two distinct edges (Formula presented.) is at least (Formula presented.). The notion of (Formula presented.) -packing edge-coloring was first generalized by Gastineau and Togni from its vertex counterpart. They showed that there are subcubic graphs that are not (Formula presented.) -packing (abbreviated to (Formula presented.) -packing) edge-colorable and asked the question whether every subcubic graph is (Formula presented.) -packing edge-colorable. Very recently, Hocquard, Lajou, and Lužar showed that every subcubic graph is (Formula presented.) -packing edge-colorable and every 3-edge-colorable subcubic graph is (Formula presented.) -packing edge-colorable. Furthermore, they also conjectured that every subcubic graph is (Formula presented.) -packing edge-colorable. In this paper, we confirm the conjecture of Hocquard, Lajou, and Lužar, and extend it to multigraphs.
AB - For a nondecreasing sequence (Formula presented.) of positive integers, an (Formula presented.) -packing edge-coloring of a graph (Formula presented.) is a decomposition of edges of (Formula presented.) into disjoint sets (Formula presented.) such that for each (Formula presented.) the distance between any two distinct edges (Formula presented.) is at least (Formula presented.). The notion of (Formula presented.) -packing edge-coloring was first generalized by Gastineau and Togni from its vertex counterpart. They showed that there are subcubic graphs that are not (Formula presented.) -packing (abbreviated to (Formula presented.) -packing) edge-colorable and asked the question whether every subcubic graph is (Formula presented.) -packing edge-colorable. Very recently, Hocquard, Lajou, and Lužar showed that every subcubic graph is (Formula presented.) -packing edge-colorable and every 3-edge-colorable subcubic graph is (Formula presented.) -packing edge-colorable. Furthermore, they also conjectured that every subcubic graph is (Formula presented.) -packing edge-colorable. In this paper, we confirm the conjecture of Hocquard, Lajou, and Lužar, and extend it to multigraphs.
KW - S-packing edge-coloring
KW - strong edge-coloring
KW - subcubic graphs
UR - http://www.scopus.com/inward/record.url?scp=85164668269&partnerID=8YFLogxK
U2 - 10.1002/jgt.23004
DO - 10.1002/jgt.23004
M3 - Article
AN - SCOPUS:85164668269
SN - 0364-9024
VL - 104
SP - 851
EP - 885
JO - Journal of Graph Theory
JF - Journal of Graph Theory
IS - 4
ER -