The packing-coloring conjecture for bounded-degree graphs

About 1 year old · traced to

Let k≥3k\geq 3, and let a kk-degree graph mean a graph of maximum degree at most kk. A coloring is (1k−1,2k−1,3)(1^{k-1},2^{k-1},3)-packing colorable if its vertices can be partitioned into k−1k-1 color classes in which distinct vertices have distance at least 22, k−1k-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 (1k−1,2k−1,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.

References

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.