Packing chromatic number under local changes in a graph

Abstract

The packing chromatic number ${\chi }_{\rho }(G)$ of a graph $G$ is the smallest integer $k$ such that there exists a $k$-vertex coloring of $G$ in which any two vertices receiving color $i$ are at distance at least $i+1$. It is proved that in the class of subcubic graphs the packing chromatic number is bigger than $13$, thus answering an open problem from [Gastineau, Togni, $S$-packing colorings of cubic graphs, Discrete Math.\ 339 (2016) 2461--2470]. In addition, the packing chromatic number is investigated with respect to several local operations. In particular, if $S_e(G)$ is the graph obtained from a graph $G$ by subdividing its edge $e$, then $\lfloor {\chi }_{\rho }(G)/2\rfloor +1\le {\chi }_{\rho }(S_e(G))\le {\chi }_{\rho }(G)+1$.

11 pages, 4 figures

References in corpus (1)

• Packing coloring of some undirected and oriented coronae graphs

Cited by in corpus (1)

• Packing chromatic number, $(1,1,2,2)$-colorings, and characterizing the Petersen graph