A characterization of $4$-${\chi }_{\rho }$-(vertex-)critical graphs

Abstract

Given a graph $G$, a function $c:V(G)⟶\{1,\dots ,k\}$ with the property that $c(u)=c(v)=i$ implies that the distance between $u$ and $v$ is greater than $i$, is called a $k$-packing coloring of $G$. The smallest integer $k$ for which there exists a $k$-packing coloring of $G$ is called the packing chromatic number of $G$, and is denoted by ${\chi }_{\rho }$. Packing chromatic vertex-critical graphs are the graphs $G$ for which ${\chi }_{\rho }(G-x)<{\chi }_{\rho }(G)$ holds for every vertex $x$ of $G$. A graph $G$ is called a packing chromatic critical graph if for every proper subgraph $H$ of $G$, ${\chi }_{\rho }(H)<{\chi }_{\rho }(G)$. Both of the mentioned variations of critical graphs with respect to the packing chromatic number have already been studied. All packing chromatic (vertex-)critical graphs $G$ with ${\chi }_{\rho }(G)=3$ were characterized, while there were known only partial results for graphs $G$ with ${\chi }_{\rho }(G)=4$. In this paper, we provide characterizations of all packing chromatic vertex-critical graphs $G$ with ${\chi }_{\rho }(G)=4$ and all packing chromatic critical graphs $G$ with ${\chi }_{\rho }(G)=4$.

/