\(S\)-packing chromatic vertex-critical graphs (Q2197411)

A packing \(k\)-colouring of a graph \(G\) with colours \(1,2,\ldots, k\) is a mapping \(c:[k]\rightarrow V(G)\) such that distinct vertices of colour \(\ell\) must have a distance between them which is greater than \(\ell\). The packing chromatic number \(\chi_p(G)\) is the smallest \(k\) for which a packing \(k\)-colouring exists. This concept was introduced in [\textit{W. Goddard} et al., Ars Comb. 86, 33--49 (2008; Zbl 1224.05172)]. It was then generalized in [\textit{W. Goddard} and \textit{H. Xu}, Discuss. Math., Graph Theory 32, No. 4, 795--806 (2012; Zbl 1293.05106)] by introducing a non-decreasing sequence \(S=[s_1,s_2,s_3,\ldots]\) so that distinct vertices of colour \(\ell\) must be at a distance greater than \(s_\ell\). The \(S\)-packing chromatic number \(\chi_S(G)\) is the smallest \(k\) for which an \(S\)-packing \(k\)-colouring exists. Note that \(S=[1,1,1,\ldots]\) corresponds to the usual idea of graph colouring, while \(S=[1,2,3,\ldots]\) corresponds to packing \(k\)-colourings. The current paper deals with critical graphs, i.e., packing critical graphs: \(\chi_p(G-u)<\chi_p(G)\), for all vertices \(u\); and \(S\)-packing critical graphs: \(\chi_S(G-u)<\chi_S(G)\), for all vertices \(u\). It is shown that if \(G\) is \(\chi_S\)-critical, then the set \(\{\chi_S(G) - \chi_S(G-u)\mid u\in V (G)\}\) can be almost arbitrary. \(\chi_S\)-critical graphs with \(k=3\) are characterized. Those with \(k=4\) are partially characterized. The criticality of trees and caterpillars is also addressed. The proofs are based on constructions for critical graphs with desired properties.