The subdivision packing-coloring conjecture for subcubic graphs

Let GG be a subcubic graph, meaning that every vertex of GG has degree at most 33, and let S(G)S(G) be the graph obtained by subdividing every edge of GG exactly once. A (1,2,3,4,5)(1,2,3,4,5)-packing coloring assigns one of five colors to the vertices so that vertices receiving color ii are pairwise at distance greater than ii.

Subdivision packing-coloring conjecture. The graph S(G)S(G) admits a (1,2,3,4,5)(1,2,3,4,5)-packing coloring. Equivalently, every subdivision of a subcubic graph has packing chromatic number at most 55.

This conjecture was posed by Brešar, Klavžar, Rall, and Wash following a question of Gastineau and Togni. The supplied source evidence establishes it for generalized prisms of a cycle, except for the Petersen graph; the general statement is therefore recorded as solved according to the supplied status.

Sources & referencesView supporting material

Primary source

Boštjan Brešar, Kirsti Kuenzel and Douglas F. Rall, “Claw-free cubic graphs are (1, 1, 2, 2)-colorable”, arXiv:2409.15455 (2024).

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.