2026-08-14T23:18:00Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16695 2024-03-06T10:58:04Z ddc:004 open_access

The Packing Chromatic Number of the Infinite Square Grid Is at Least 14 Subercaseaux, Bernardo Heule, Marijn J.H. packing coloring SAT solvers encodings 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Bernardo Subercaseaux and Marijn J.H. Heule 2022 Is Part Of LIPIcs, Volume 236, 25th International Conference on Theory and Applications of Satisfiability Testing (SAT 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SAT.2022.21 urn:nbn:de:0030-drops-166951 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAT.2022.21 eng https://creativecommons.org/licenses/by/4.0/legalcode