Packing chromatic number of subdivisions of cubic graphs

Abstract

A packing $k$-coloring of a graph $G$ is a partition of $V(G)$ into sets $V_1,\dots ,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, Klavzar, 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$.

20 pages, 15 figures