Packing chromatic critical graphs with radius at most 2

Abstract

For a graph $G$ with vertex set $V(G)$ and a positive integer $i$, an $i$-packing in $G$ is a subset $X$ of $V(G)$ such that the distance between any two distinct vertices of $X$ is greater than $i$. The packing chromatic number of $G$, denoted by ${\chi }_{\rho }(G)$, is the smallest positive integer $k$ for which there exists a partition $X_1,X_2,\dots ,X_k$ of $V(G)$ such that $X_i$ is an $i$-packing in $G$ for every $i\in [k]$. A graph $G$ is called ${\chi }_{\rho }$-critical if ${\chi }_{\rho }(H)<{\chi }_{\rho }(G)$ holds for every proper subgraph $H$ of $G$. In this paper, we provide a structural characterization of ${\chi }_{\rho }$-critical graphs with radius $1$, and completely determine the ${\chi }_{\rho }$-critical cactus graphs with radius $2$ and diameter $2$ or $3$.