License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SAT.2022.21
URN: urn:nbn:de:0030-drops-166951
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16695/
Subercaseaux, Bernardo ;
Heule, Marijn J.H.
The Packing Chromatic Number of the Infinite Square Grid Is at Least 14
Abstract
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.
BibTeX - Entry
@InProceedings{subercaseaux_et_al:LIPIcs.SAT.2022.21,
author = {Subercaseaux, Bernardo and Heule, Marijn J.H.},
title = {{The Packing Chromatic Number of the Infinite Square Grid Is at Least 14}},
booktitle = {25th International Conference on Theory and Applications of Satisfiability Testing (SAT 2022)},
pages = {21:1--21:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-242-6},
ISSN = {1868-8969},
year = {2022},
volume = {236},
editor = {Meel, Kuldeep S. and Strichman, Ofer},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16695},
URN = {urn:nbn:de:0030-drops-166951},
doi = {10.4230/LIPIcs.SAT.2022.21},
annote = {Keywords: packing coloring, SAT solvers, encodings}
}
