1 Search Results for "Heule, Marijn J.H."

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-dev.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}
}
  • Refine by Author
  • 1 Heule, Marijn J.H.
  • 1 Subercaseaux, Bernardo

  • Refine by Classification
  • 1 Mathematics of computing → Combinatoric problems

  • Refine by Keyword
  • 1 SAT solvers
  • 1 encodings
  • 1 packing coloring

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2022

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact