Packing chromatic number under local changes in a graph

The packing chromatic number $χ_ρ(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 $\left\lfloor χ_ρ(G)/2 \right\rfloor +1 \le χ_ρ(S_e(G)) \le χ_ρ(G)+1$.

No reviews yet.

No comments yet.