The packing chromatic number of the square lattice is at least 12

Abstract

The packing chromatic number ${\chi }_{\rho }(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$, where vertices in $X_i$ have pairwise distance greater than $i$. For the 2-dimensional square lattice ${\mathbb{Z}}^2$ it is proved that ${\chi }_{\rho }({\mathbb{Z}}^2)\ge 12$, which improves the previously known lower bound 10.

arXiv comment3 pages