The packing-coloring conjecture for bounded-degree graphs
The packing-coloring conjecture for bounded-degree graphs
Let , and let a -degree graph mean a graph of maximum degree at most . A coloring is -packing colorable if its vertices can be partitioned into color classes in which distinct vertices have distance at least , color classes in which distinct vertices have distance at least , and one color class in which distinct vertices have distance at least . Packing-coloring conjecture. Every -degree graph is -packing colorable.
This conjecture refines the known packing-coloring result for subcubic graphs, which are -packing colorable. The proposed statement concerns all graphs of maximum degree at least three; its resolution is not specified in the source.
Sources & referencesView supporting material
Primary source
Maidoun Mortada and Olivier Togni, “On S-packing Coloring of Bounded Degree Graphs”, arXiv:2503.18793 (2025).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.