The Packing Coloring of Distance Graphs $D(k,t)$

Abstract

The packing chromatic number ${\chi }_{\rho }(G)$ of a graph $G$ is the smallest integer $p$ such that vertices of $G$ can be partitioned into disjoint classes $X_1,...,X_p$ where vertices in $X_i$ have pairwise distance greater than $i$. For $k<t$ we study the packing chromatic number of infinite distance graphs $D(k,t)$, i.e. graphs with the set $\mathbb{Z}$ of integers as vertex set and in which two distinct vertices $i,j\in \mathbb{Z}$ are adjacent if and only if $|i-j|\in \{k,t\}$. We generalize results by Ekstein et al. for graphs $D(1,t)$. For sufficiently large $t$ we prove that ${\chi }_{\rho }(D(k,t))\le 30$ for both $k$, $t$ odd, and that ${\chi }_{\rho }(D(k,t))\le 56$ for exactly one of $k$, $t$ odd. We also give some upper and lower bounds for ${\chi }_{\rho }(D(k,t))$ with small $k$ and $t$. Keywords: distance graph; packing coloring; packing chromatic number

15 pages