DROPS

Document

DOI: 10.4230/LIPIcs.SAT.2022.21

The Packing Chromatic Number of the Infinite Square Grid Is at Least 14

Authors: Bernardo Subercaseaux and Marijn J.H. Heule

Published in: LIPIcs, Volume 236, 25th International Conference on Theory and Applications of Satisfiability Testing (SAT 2022)

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.

Cite as

Bernardo Subercaseaux and Marijn J.H. Heule. The Packing Chromatic Number of the Infinite Square Grid Is at Least 14. In 25th International Conference on Theory and Applications of Satisfiability Testing (SAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 236, pp. 21:1-21:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.SAT.2022.21},
  URN =		{urn:nbn:de:0030-drops-166951},
  doi =		{10.4230/LIPIcs.SAT.2022.21},
  annote =	{Keywords: packing coloring, SAT solvers, encodings}
}

Search Results

Documents authored by Heule, Marijn J.H.

The Packing Chromatic Number of the Infinite Square Grid Is at Least 14

Abstract

Cite as

Thanks for your feedback!

Could not send message