$S$-packing colorings of distance graphs with distance sets of cardinality $2$

Abstract

For a non-decreasing sequence $S=(s_1,s_2,\dots )$ of positive integers, a partition of the vertex set of a graph $G$ into subsets $X_1,\dots ,X_{\ell }$, such that vertices in $X_i$ are pairwise at distance greater than $s_i$ for every $i\in \{1,\dots ,\ell \}$, is called an $S$-packing $\ell$-coloring of $G$. The minimum $\ell$ for which $G$ admits an $S$-packing $\ell$-coloring is called the $S$-packing chromatic number of $G$, denoted by ${\chi }_S(G)$. In this paper, we consider $S$-packing colorings of distance graphs $G(\mathbb{Z},\{k,t\})$, where $k$ and $t$ are positive integers, which are the graphs whose vertex set is $\mathbb{Z}$, and two vertices $x,y\in \mathbb{Z}$ are adjacent whenever $|x-y|\in \{k,t\}$. We complement partial results from two earlier papers, thus determining all values of ${\chi }_S(G(\mathbb{Z},\{k,t\}))$ when $S$ is any sequence with $s_i\le 2$ for all $i$. In particular, if $S=(1,1,2,2,\dots )$, then the $S$-packing chromatic number is $2$ if $k+t$ is even, and $4$ otherwise, while if $S=(1,2,2,\dots )$, then the $S$-packing chromatic number is $5$, unless $\{k,t\}=\{2,3\}$ when it is $6$; when $S=(2,2,2,\dots )$, the corresponding formula is more complex.