$S$-packing chromatic vertex-critical graphs

Abstract

For a non-decreasing sequence of positive integers $S=(s_1,s_2,\dots )$, the {\em $S$-packing chromatic number} ${\chi }_S(G)$ of $G$ is the smallest integer $k$ such that the vertex set of $G$ can be partitioned into sets $X_i$, $i\in [k]$, where vertices in $X_i$ are pairwise at distance greater than $s_i$. In this paper we introduce $S$-packing chromatic vertex-critical graphs, ${\chi }_S$-critical for short, as the graphs in which ${\chi }_S(G-u)<{\chi }_S(G)$ for every $u\in V(G)$. This extends the earlier concept of the packing chromatic vertex-critical graphs. We show that if $G$ is ${\chi }_S$-critical, then the set $\{{\chi }_S(G)-{\chi }_S(G-u);u\in V(G)\}$ can be almost arbitrary. If $G$ is ${\chi }_S$-critical and ${\chi }_S(G)=k$ ($k\in \mathbb{N}$), then $G$ is called $k$-${\chi }_S$-critical. We characterize $3$-${\chi }_S$-critical graphs and partially characterize $4$-${\chi }_S$-critical graphs when $s_1>1$. We also deal with $k$-${\chi }_S$-criticality of trees and caterpillars.