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

About 1 year old · traced to

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.

References

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.