On the packing chromatic number of square and hexagonal lattice - Korže, Danilo (Ars mathematica contemporanea, 2014)
The packing chromatic number ?$χ_p(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 ?$\mathcal{H}$? is 7. We also investigate the packing chromatic number for infinite subgraphs of the square lattice ?$\mathbb{Z}^2$? with up to 13 rows. In particular, we establish the packing chromatic number for ?$P_6 \Box \mathbb{Z}$? 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 ?$\mathbb{Z}^2 \Box P_2$?. The results are partially obtained by a computer search.
Keywords: computer search; graph theory; hexagonal lattice; packing chromatic number; square lattice; teorija grafov