The packing-coloring conjecture for bounded-degree graphs

Let k3k\geq 3, and let a kk-degree graph mean a graph of maximum degree at most kk. A coloring is (1k1,2k1,3)(1^{k-1},2^{k-1},3)-packing colorable if its vertices can be partitioned into k1k-1 color classes in which distinct vertices have distance at least 22, k1k-1 color classes in which distinct vertices have distance at least 33, and one color class in which distinct vertices have distance at least 44. Packing-coloring conjecture. Every kk-degree graph is (1k1,2k1,3)(1^{k-1},2^{k-1},3)-packing colorable.

This conjecture refines the known packing-coloring result for subcubic graphs, which are (1,1,2,2,3)(1,1,2,2,3)-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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.