On packing colorings of distance graphs

The packing chromatic number chi(rho)(G) of a graph G is the least integer k for which there exists a mapping f from V(G) to {1, 2,..., k} such that any two vertices of color i are at a distance of at least i + 1. This paper studies the packing chromatic number of infinite distance graphs G(Z, D), i.e. graphs with the set Z of integers as vertex set, with two distinct vertices i,j is an element of Z being adjacent if and only if vertical bar i - j vertical bar is an element of D. We present lower and upper bounds for chi(rho)(G(Z, D)), showing that for finite D, the packing chromatic number is finite. Our main result concerns distance graphs with D = {1, t} for which we prove some upper bounds on their packing chromatic numbers, the smaller ones being for t >= 447: chi(rho) (G(Z, {1, t})) <= 40 if t is odd and chi(rho) (G(Z, {1, t})) <= 81 if t is even. (C) 2013 Elsevier B.V. All rights reserved.