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 ₁ , … , V _k such that for each 1 ≤ i≤ k the distance between any two distinct x, y∈ V _i is at least i+ 1. The packing chromatic number, χ _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 χ _p (G) and of χ _p (D(G)) over the class of subcubic graphs G appear in several papers. Gastineau and Togni asked whether χ _p (D(G)) ≤ 5 for any subcubic G, and later Brešar, Klavžar, Rall and Wash conjectured this, but no upper bound was proved. Recently the authors proved that χ _p (G) is not bounded in the class of subcubic graphs G. In contrast, in this paper we show that χ _p (D(G)) is bounded in this class, and does not exceed 8.