A characterization of $4$-$\chi_\rho$-(vertex-)critical graphs

Abstract

Given a graph $G$, a function $c:V(G)\longrightarrow \{1,\ldots,k\}$ with the property that for every $u \neq v$, $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(G)$. 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 $\pch(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$.