The Packing Chromatic Number Is 15
On a square lattice, place 1s so that all 1s have a taxicab distance greater than 1 from each other. Next, add 2s so that the 2s all have a taxicab distance greater than 2 from each other. And so on. If the entire square lattice is filled with values, what is the maximal value in the lattice?[more]
The taxicab distance between two points and is .
This problem is known as the packing chromatic number of the infinite square lattice. It turns out the answer is 15. This Demonstration shows that the upper bound of 15 works in a grid, as seen in . In a subsequent paper , the lower bound was proven to be 15.
You can select a value using the slider.
The display options are "numbers", a grid of numbers; "lattice", a grayscale version of the numbers; and "circles", with circles around the chosen values.[less]
 B. Martin, F. Raimondi, T. Chen and J. Martin, "The Packing Chromatic Number of the Infinite Square Lattice Is between 13 and 15." arxiv.org/abs/1510.02374.
 B. Subercaseaux and M. J. H. Heule, "The Packing Chromatic Number of the Infinite Square Grid Is 15." arxiv.org/abs/2301.09757.