Packing chromatic vertex-critical graphs

Abstract

The packing chromatic number ${\chi }_{\rho }(G)$ of a graph $G$ is the smallest integer $k$ such that the vertex set of $G$ can be partitioned into sets $V_i$, $i\in [k]$, where vertices in $V_i$ are pairwise at distance at least $i+1$. Packing chromatic vertex-critical graphs, ${\chi }_{\rho }$-critical for short, are introduced as the graphs $G$ for which ${\chi }_{\rho }(G-x)<{\chi }_{\rho }(G)$ holds for every vertex $x$ of $G$. If ${\chi }_{\rho }(G)=k$, then $G$ is $k$-${\chi }_{\rho }$-critical. It is shown that if $G$ is ${\chi }_{\rho }$-critical, then the set $\{{\chi }_{\rho }(G)-{\chi }_{\rho }(G-x):x\in V(G)\}$ can be almost arbitrary. The $3$-${\chi }_{\rho }$-critical graphs are characterized, and $4$-${\chi }_{\rho }$-critical graphs are characterized in the case when they contain a cycle of length at least $5$ which is not congruent to $0$ modulo $4$. It is shown that for every integer $k\ge 2$ there exists a $k$-${\chi }_{\rho }$-critical tree and that a $k$-${\chi }_{\rho }$-critical caterpillar exists if and only if $k\le 7$. Cartesian products are also considered and in particular it is proved that if $G$ and $H$ are vertex-transitive graphs and $\mathrm{diam}(\mathrm{G})+\mathrm{diam}(H)\le {\chi }_{\rho }(G)$, then $G\square H$ is ${\chi }_{\rho }$-critical.