Brešar–Togni conjecture on packing coloring of subdivided subcubic graphs
Brešar–Togni conjecture on packing coloring of subdivided subcubic graphs
Let be a graph in which every vertex has degree at most , and let be the graph obtained by subdividing every edge of , replacing each edge by a path -- through a new vertex . Brešar–Togni conjecture. Every subcubic graph satisfies
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
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.