Every subcubic multigraph is (1,27) (1,{2}^{7})‐packing edge‐colorable

DOI10.1002/JGT.23004MaRDI QIDQ6062875zbMATH OpenFDO

Authors Xujun Liu, Michael Santana, Taylor Short

Publication date 6 November 2023

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2206.15046

zbMATH Keywords

\(S\)-packing edge-coloringstrong edge-coloringsubcubic graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: For a non-decreasing sequence $S=(s_1,ldots,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,ldots,E_k$ such that for each $1leilek$ 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 Luv{z}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 Luv{z}ar, and extend it to multigraphs.

Recommendations

• Packing \(( 1 , 1 , 2 , 2 )\)-coloring of some subcubic graphs
• On packing \(S\)-colorings of subcubic graphs
• Packing \(( 1 , 1 , 2 , 4 )\)-coloring of subcubic outerplanar graphs
• Packing colorings of subcubic outerplanar graphs
• On edge colorings with at least \(q\) colors in every subset of \(p\) vertices
• On S-packing edge-colorings of cubic graphs
• A concise proof for total coloring subcubic graphs
• On strong edge-colouring of subcubic graphs
• Injective edge-coloring of subcubic graphs
• An infinite family of subcubic graphs with unbounded packing chromatic number

Cites work

• \(S\)-packing colorings of cubic graphs
• A bound on the strong chromatic index of a graph
• An infinite family of subcubic graphs with unbounded packing chromatic number
• Between Proper and Strong Edge-Colorings of Subcubic Graphs
• Between proper and strong edge‐colorings of subcubic graphs
• scientific article; zbMATH DE number 3851125 (Why is no real title available?)
• Induced matchings in cubic graphs
• On S-packing edge-colorings of cubic graphs
• On induced matchings
• Packing chromatic number of cubic graphs
• Packing chromatic number of subdivisions of cubic graphs
• Packing chromatic number under local changes in a graph
• Strong chromatic index of graphs with maximum degree four
• Strong chromatic index of subcubic planar multigraphs
• Strong edge colorings of graphs and the covers of Kneser graphs
• Strong edge-coloring for planar graphs with large girth
• Strong edge-colorings of sparse graphs with large maximum degree
• The packing chromatic number of infinite product graphs
• The strong chromatic index of a cubic graph is at most 10
• The Strong Chromatic Index of Random Graphs

Cited in

(9)

• On S-packing edge-coloring of graphs with given edge weight
• On the (1, 2⁵)-packing edge-colorings of claw-free subcubic graphs
• Claw-free cubic graphs are (1, 1, 1, 3)-packing edge-colorable
• On S-packing edge-colorings of subcubic claw-free graphs
• Every subcubic graph is packing (1,1,2,2,3)-colorable
• Every graph with maximum degree at most four is \((1^1,2^{19})\)-packing edge-colorable and \((1^2,2^{17})\)-packing edge-colorable
• Every cubic Halin graph is (1, 2⁶)-packing edge-colorable
• Packing edge-colorings of subcubic outerplanar graphs
• On the packing edge-colorings of subcubic K₄-minor free graphs

This page was built for publication: Every subcubic multigraph is (1,27) $(1,{2}^{7})$‐packing edge‐colorable

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6062875)