Brešar–Togni conjecture on packing coloring of subdivided subcubic graphs

Let GG be a graph in which every vertex has degree at most 33, and let S(G)S(G) be the graph obtained by subdividing every edge of GG, replacing each edge uvuv by a path uu-ww-vv through a new vertex ww. Brešar–Togni conjecture. Every subcubic graph satisfies

χp(S(G))5.\chi_p(S(G))\leq 5.

This conjecture asks for a universal upper bound on the packing chromatic number of the subdivision of a subcubic graph. It arose from work of Gastineau and Togni and was subsequently formalized by Brešar et al.; its resolution is not specified in the source.

Sources & referencesView supporting material

Primary source

Xin Zhang and Dezhi Zou, “Fast algorithm for S-packing coloring of Halin graphs”, arXiv:2512.22809 (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.