Brešar, Klavžar, Rall, and Wаsh's packing-coloring conjecture for subdivided subcubic graphs

Let GG be a subcubic graph, meaning that its maximum degree is at most 33. Let D(G)D(G) be the graph obtained by subdividing every edge of GG, and let χp(G)\chi_p(G) denote the packing chromatic number, the smallest kk such that GG has a packing (1,2,,k)(1,2,\ldots,k)-coloring. Brešar, Klavžar, Rall, and Wash's conjecture. For every subcubic graph GG,

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

The conjecture concerns a uniform upper bound on the packing chromatic number after subdividing every edge of a subcubic graph. It was motivated by an earlier question of Gastineau and Togni and was subsequently conjectured by Brešar, Klavžar, Rall, and Wash; the supplied source gives no resolution, so its status remains open.

Sources & referencesView supporting material

Primary source

Runrun Liu, Xujun Liu, Martin Rolek and Gexin Yu, “Packing (1,1,2,2)-coloring of some subcubic graphs”, arXiv:1911.03824 (2019).

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.