On packing colorings of distance graphs

The packing chromatic number  χρ(G)χρ(G) of a graph GG is the least integer kk for which there exists a mapping ff from V(G)V(G) to {1,2,…,k}{1,2,…,k} such that any two vertices of color ii are at a distance of at least i+1i+1. This paper studies the packing chromatic number of infinite distance graphs G(Z,D)G(Z,D), i.e. graphs with the set ZZ of integers as vertex set, with two distinct vertices i,j∈Zi,j∈Z being adjacent if and only if ∣i−j∣∈D∣i−j∣∈D. We present lower and upper bounds for χρ(G(Z,D))χρ(G(Z,D)), showing that for finite DD, the packing chromatic number is finite. Our main result concerns distance graphs with D={1,t}D={1,t} for which we prove some upper bounds on their packing chromatic numbers, the smaller ones being for t≥447t≥447: χρ(G(Z,{1,t}))≤40χρ(G(Z,{1,t}))≤40 if tt is odd and χρ(G(Z,{1,t}))≤81χρ(G(Z,{1,t}))≤81 if tt is even.