Brešar, Klavžar, Rall, and Wash's packing chromatic number conjecture for subdivisions of subcubic graphs

Let GG be a subcubic graph, and let D(G)D(G) denote its subdivision, obtained by replacing each edge of GG by a path of length two. The packing chromatic number χp(G)\chi_p(G) is the minimum kk for which GG has a packing (1,2,,k)(1,2,\ldots,k)-coloring, where a packing (s1,s2,,sk)(s_1,s_2,\ldots,s_k)-coloring partitions the vertex set into classes V1,V2,,VkV_1,V_2,\ldots,V_k such that the distance between distinct vertices in ViV_i is at least si+1s_i+1. Brešar, Klavžar, Rall, and Wash's conjecture. The subdivision satisfies

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

This conjecture concerns whether the packing chromatic number is uniformly bounded for subdivisions of subcubic graphs; the source presents it as a conjecture following an earlier question by Gastineau and Togni, and does not state a resolution.

Sources & referencesView supporting material

Primary source

Alexandr Kostochka and Xujun Liu, “Packing (1,1,2,4)-coloring of subcubic outerplanar graphs”, arXiv:2005.04803 (2021).

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.