Packing Chromatic Number of Subdivisions of Cubic Graphs.

A packing k-coloring of a graph G is a partition of V(G) into sets V1,...,Vk such that for each 1≤i≤k the distance between any two distinct x,y∈Vi 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. [ABSTRACT FROM AUTHOR]