Graphs that are critical for the packing chromatic number

Abstract

Given a graph $G$, a coloring $c:V(G)⟶\{1,\dots ,k\}$ such that $c(u)=c(v)=i$ implies that vertices $u$ and $v$ are at distance greater than $i$, is called a packing coloring of $G$. The minimum number of colors in a packing coloring of $G$ is called the packing chromatic number of $G$, and is denoted by ${\chi }_{\rho }(G)$. In this paper, we propose the study of ${\chi }_{\rho }$-critical graphs, which are the graphs $G$ such that for any proper subgraph $H$ of $G$, ${\chi }_{\rho }(H)<{\chi }_{\rho }(G)$. We characterize ${\chi }_{\rho }$-critical graphs with diameter 2, and ${\chi }_{\rho }$-critical block graphs with diameter 3. Furthermore, we characterize ${\chi }_{\rho }$-critical graphs with small packing chromatic numbers, and we also consider ${\chi }_{\rho }$-critical trees. In addition, we prove that for any graph $G$ with $e\in E(G)$, we have $({\chi }_{\rho }(G)+1)/2\le {\chi }_{\rho }(G-e)\le {\chi }_{\rho }(G)$, and provide a corresponding realization result, which shows that ${\chi }_{\rho }(G-e)$ can achieve any of the integers between the bounds.

19 pages, 1 figure