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