Packing Chromatic Number of Subdivisions of Cubic Graphs

A packing k-coloring of a graph G is a partition of V(G) into sets \(V_1,\ldots ,V_k\) such that for each \(1\le i\le k\) the distance between any two distinct \(x,y\in V_i\) is at least \(i+1\). The packing chromatic number, \(\chi _p(G)\), of a graph G is the minimum k such that G has a packing k-coloring. For a graph G, let D(G) denote the graph obtained from G by subdividing every edge. The questions on the value of the maximum of \(\chi _p(G)\) and of \(\chi _p(D(G))\) over the class of subcubic graphs G appear in several papers. Gastineau and Togni asked whether \(\chi _p(D(G))\le 5\) for any subcubic G, and later Bresar, Klavžar, Rall and Wash conjectured this, but no upper bound was proved. Recently the authors proved that \(\chi _p(G)\) is not bounded in the class of subcubic graphs G. In contrast, in this paper we show that \(\chi _p(D(G))\) is bounded in this class, and does not exceed 8.