Interesting Esoterica

The Packing Chromatic Number of the Infinite Square Grid is 15

Article by Bernardo Subercaseaux and Marijn J. H. Heule
  • Published in 2023
  • Added on
In the collections
A packing $k$-coloring is a natural variation on the standard notion of graph $k$-coloring, where vertices are assigned numbers from $\{1, \ldots, k\}$, and any two vertices assigned a common color $c \in \{1, \ldots, k\}$ need to be at a distance greater than $c$ (as opposed to $1$, in standard graph colorings). Despite a sequence of incremental work, determining the packing chromatic number of the infinite square grid has remained an open problem since its introduction in 2002. We culminate the search by proving this number to be 15. We achieve this result by improving the best-known method for this problem by roughly two orders of magnitude. The most important technique to boost performance is a novel, surprisingly effective propositional encoding for packing colorings. Additionally, we developed an alternative symmetry-breaking method. Since both new techniques are more complex than existing techniques for this problem, a verified approach is required to trust them. We include both techniques in a proof of unsatisfiability, reducing the trusted core to the correctness of the direct encoding.

Links

Other information

key
ThePackingChromaticNumberoftheInfiniteSquareGridis15
type
article
date_added
2023-01-26
date_published
2023-05-24

BibTeX entry

@article{ThePackingChromaticNumberoftheInfiniteSquareGridis15,
	key = {ThePackingChromaticNumberoftheInfiniteSquareGridis15},
	type = {article},
	title = {The Packing Chromatic Number of the Infinite Square Grid is 15},
	author = {Bernardo Subercaseaux and Marijn J. H. Heule},
	abstract = {A packing {\$}k{\$}-coloring is a natural variation on the standard notion of graph
{\$}k{\$}-coloring, where vertices are assigned numbers from {\$}\{\{}1, \ldots, k\{\}}{\$}, and
any two vertices assigned a common color {\$}c \in \{\{}1, \ldots, k\{\}}{\$} need to be at
a distance greater than {\$}c{\$} (as opposed to {\$}1{\$}, in standard graph colorings).
Despite a sequence of incremental work, determining the packing chromatic
number of the infinite square grid has remained an open problem since its
introduction in 2002. We culminate the search by proving this number to be 15.
We achieve this result by improving the best-known method for this problem by
roughly two orders of magnitude. The most important technique to boost
performance is a novel, surprisingly effective propositional encoding for
packing colorings. Additionally, we developed an alternative symmetry-breaking
method. Since both new techniques are more complex than existing techniques for
this problem, a verified approach is required to trust them. We include both
techniques in a proof of unsatisfiability, reducing the trusted core to the
correctness of the direct encoding.},
	comment = {},
	date_added = {2023-01-26},
	date_published = {2023-05-24},
	urls = {http://arxiv.org/abs/2301.09757v1,http://arxiv.org/pdf/2301.09757v1},
	collections = {combinatorics,fun-maths-facts},
	url = {http://arxiv.org/abs/2301.09757v1 http://arxiv.org/pdf/2301.09757v1},
	year = 2023,
	urldate = {2023-01-26},
	archivePrefix = {arXiv},
	eprint = {2301.09757},
	primaryClass = {cs.DM}
}