S-packing chromatic critical graphs

Abstract

For a non-decreasing sequence of positive integers $S=(s_1,s_2,\dots )$, the $S$-packing chromatic number of a graph $G$ is denoted by ${\chi }_S(G)$. In this paper, ${\chi }_S$-critical graphs are introduced as the graphs $G$ such that ${\chi }_S(H)<{\chi }_S(G)$ for each proper subgraph $H$ of $G$. Several families of ${\chi }_S$-critical graphs are constructed, and $2$- and $3$-colorable ${\chi }_S$-critical graphs are presented for all packing sequences $S$, while $4$-colorable ${\chi }_S$-critical graphs are found for most of $S$. Cycles which are ${\chi }_S$-critical are characterized under different conditions. It is proved that for any graph $G$ and any edge $e\in E(G)$, the inequality ${\chi }_S(G-e)\ge {\chi }_S(G)/2$ holds. Moreover, in several important cases, this bound can be improved to ${\chi }_S(G-e)\ge ({\chi }_S(G)+1)/2$. The sharpness of the bounds is also discussed. Along the way an earlier result on ${\chi }_S$-vertex-critical graphs is supplemented.