A characterization of 4-${\chi }_S$-vertex-critical graphs for packing sequences with $s_1=1$ and $s_2\ge 3$

Abstract

If $S=(s_1,s_2,\dots )$ is a non-decreasing sequence of positive integers, then the $S$-packing $k$-coloring of a graph $G$ is a mapping $c:V(G)\to [k]$ such that if $c(u)=c(v)=i$ for $u\ne v\in V(G)$, then $d_G(u,v)>s_i$. The $S$-packing chromatic number of $G$ is the smallest integer $k$ such that $G$ admits an $S$-packing $k$-coloring. A graph $G$ is ${\chi }_S$-vertex-critical if ${\chi }_S(G-u)<{\chi }_S(G)$ for each $u\in V(G)$. If $G$ is ${\chi }_S$-vertex-critical and ${\chi }_S(G)=k$, then $G$ is $k$-${\chi }_S$-vertex-critical. In this paper, $4$-${\chi }_S$-vertex-critical graphs are characterized for sequences $S=(1,s_2,s_3,\dots )$ with $s_2\ge 3$. There are $28$ sporadic examples and two infinite families of such graphs.

arXiv comment19 pages, 2 figures