The Packing Chromatic Number of the Infinite Square Grid Is at Least 14
Jan Ekstein, Jiřı́ Fiala, Přemysl Holub, Bernard Lidický · arXiv (Cornell University) · 2010
A packing k-coloring of a graph G = (V, E) is a mapping from V to {1, ..., k} such that any pair of vertices u, v that receive the same color c must be at distance greater than c in G. Arguably the most fundamental problem regarding packing colorings is to determine the packing chromatic number of the infinite square grid. A sequence of previous works has proved this number to be between 13 and 15. Our work improves the lower bound to 14. Moreover, we present a new encoding that is asymptotically more compact than the previously used ones.