The packing chromatic number of infinite product graphs

The packing chromatic number χρ(G)χρ(G) of a graph GG is the smallest integer kk such that the vertex set V(G)V(G) can be partitioned into disjoint classes X1,…,XkX1,…,Xk, where vertices in XiXi have pairwise distance greater than ii. For the Cartesian product of a path and the two-dimensional square lattice it is proved that χρ(Pm□Z2)=∞χρ(Pm□Z2)=∞ for any m≥2m≥2, thus extending the result χρ(Z3)=∞χρ(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χρ(Z2)≥10 which improves the bound χρ(Z2)≥9χρ(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)<∞χρ(G□Z)<∞ for any finite graph GG. The infinite hexagonal lattice HH is also considered and it is proved that χρ(H)≤7χρ(H)≤7 and χρ(Pm□H)=∞χρ(Pm□H)=∞ for m≥6m≥6.