The subdivision packing-coloring conjecture for subcubic graphs
The subdivision packing-coloring conjecture for subcubic graphs
Let be a subcubic graph, meaning that every vertex of has degree at most , and let be the graph obtained by subdividing every edge of exactly once. A -packing coloring assigns one of five colors to the vertices so that vertices receiving color are pairwise at distance greater than .
Subdivision packing-coloring conjecture. The graph admits a -packing coloring. Equivalently, every subdivision of a subcubic graph has packing chromatic number at most .
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
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.