On the packing chromatic number of square and hexagonal lattice

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 X₁, …, 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 ℤ ² with up to 13 rows. In particular, we establish the packing chromatic number for P₆□ ℤ 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 ℤ ²□ P₂. The results are partially obtained by a computer search.