Creative Commons Attribution 4.0 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: https://drops.dagstuhl.de/opus/volltexte/2022/16695/
Subercaseaux, Bernardo ; Heule, Marijn J.H.
The Packing Chromatic Number of the Infinite Square Grid Is at Least 14
| pdf-format: |
|
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}
}
| Keywords: | packing coloring, SAT solvers, encodings | |
| Seminar: | 25th International Conference on Theory and Applications of Satisfiability Testing (SAT 2022) | |
| Issue date: | 2022 | |
| Date of publication: | 28.07.2022 | |
| Supplementary Material: | Software (Source Code): https://github.com/bsubercaseaux/PackingChromaticNumberAtLeast14 archived at: https://archive.softwareheritage.org/swh:1:dir:45141aa52bb50ce1bd8379e07aca744f9c6eac40 |
