Skip to main content
Article
The packing chromatic number of infinite product graphs
European Journal of Combinatorics (2009)
  • Jiří Fiala, Charles University
  • Sandi Klavžar, University of Ljubljana
  • Bernard Lidicky, Charles University
Abstract
The 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.
Publication Date
July, 2009
DOI
10.1016/j.ejc.2008.09.014
Publisher Statement
This is a manuscript of an article from Fiala, Jiří, Sandi Klavžar, and Bernard Lidický. "The packing chromatic number of infinite product graphs." European Journal of Combinatorics 30, no. 5 (2009): 1101-1113. DOI: 10.1016/j.ejc.2008.09.014. Copyright 2008 Elsevier Ltd. Posted with permission.
Citation Information
Jiří Fiala, Sandi Klavžar and Bernard Lidicky. "The packing chromatic number of infinite product graphs" European Journal of Combinatorics Vol. 30 Iss. 5 (2009) p. 1101 - 1113
Available at: http://works.bepress.com/bernard-lidicky/24/