The packing coloring of distance graphs D(k, t)

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 between them 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 Z of integers as vertex set and in which two distinct vertices i, j is an element of Z are adjacent if and only if vertical bar i - j vertical bar is an element of (k, t). We generalize results given by Ekstein et al. for graphs D(1, t). For sufficiently large t we prove that chi(rho)(D(k, t)) <= 30 for both k and t odd, and that chi(rho)(D(k, t)) <= 56 for exactly one of k and t odd. We also give some upper and lower bounds for chi(rho)(D(k, t)) with small k and t. (C) 2013 Elsevier B.V. All rights reserved.