The packing chromatic number of infinite product graphs

AbstractThe packing chromatic number χρ(G) of a graph G is the smallest integer k such that the vertex set V(G) can be partitioned into disjoint classes X1,…,Xk, where vertices in Xi have pairwise distance greater than i. For the Cartesian product of a path and the two-dimensional square lattice it is proved that χρ(Pm□Z2)=∞ for any m≥2, thus extending the result χρ(Z3)=∞ of [A. Finbow, D.F. Rall, On the packing chromatic number of some lattices, Discrete Appl. Math. (submitted for publication) special issue LAGOS’07]. It is also proved that χρ(Z2)≥10 which improves the bound χρ(Z2)≥9 of [W. Goddard, S.M. Hedetniemi, S.T. Hedetniemi, J.M. Harris, D.F. Rall, Broadcast chromatic numbers of graphs, Ars Combin. 86 (2008) 33–49]. Moreover, it is shown that χρ(G□Z)<∞ for any finite graph G. The infinite hexagonal lattice H is also considered and it is proved that χρ(H)≤7 and χρ(Pm□H)=∞ for m≥6