Packing Chromatic Number of Distance Graphs

Abstract

The packing chromatic number ${\chi }_{\rho }(G)$ of a graph $G$ is the smallest integer $k$ such that vertices of $G$ can be partitioned into disjoint classes $X_1,...,X_k$ where vertices in $X_i$ have pairwise distance greater than $i$. We study the packing chromatic number of infinite distance graphs $G(Z,D)$, i.e. graphs with the set $Z$ of integers as vertex set and in which two distinct vertices $i,j\in Z$ are adjacent if and only if $|i-j|\in D$. In this paper we focus on distance graphs with $D=\{1,t\}$. We improve some results of Togni who initiated the study. It is shown that ${\chi }_{\rho }(G(Z,D))\le 35$ for sufficiently large odd $t$ and ${\chi }_{\rho }(G(Z,D))\le 56$ for sufficiently large even $t$. We also give a lower bound 12 for $t\ge 9$ and tighten several gaps for ${\chi }_{\rho }(G(Z,D))$ with small $t$.

13 pages, 3 figures