On the packing chromatic number of square and hexagonal lattice
Danilo Korže, Aleksander Vesel · Ars Mathematica Contemporanea · 2013
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 X 1 , …, X k , with the condition that vertices in X i have pairwise distance greater than i . We show that the packing chromatic number for the hexagonal lattice ℋ is 7. We also investigate the packing chromatic number for infinite subgraphs of the square lattice ℤ 2 with up to 13 rows. In particular, we establish the packing chromatic number for P 6 □ ℤ and provide new upper bounds on these numbers for the other subgraphs of interest. Finally, we explore the packing chromatic number for some infinite subgraphs of ℤ 2 □ P 2 . The results are partially obtained by a computer search.