Document Open Access Logo

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

Authors Bernardo Subercaseaux , Marijn J.H. Heule

PDF

File

Thumbnail PDF
PDF
LIPIcs.SAT.2022.21.pdf
  • Filesize: 0.79 MB
  • 16 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Combinatoric problems
Keywords
  • packing coloring
  • SAT solvers
  • encodings

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

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 Get BibTex

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) https://doi.org/10.4230/LIPIcs.SAT.2022.21

Author Details

Bernardo Subercaseaux
  • Carnegie Mellon University, Pittsburgh, PA, USA
Marijn J.H. Heule
  • Carnegie Mellon University, Pittsburgh, PA, USA

Funding

Authors are supported by National Science Foundation grant CCF-2015445.

Acknowledgements

Authors thank the Pittsburgh Supercomputing Center for allowing us to use Bridges2 [Brown et al., 2021] in our experiments. The first author thanks Dylan Pizzo for his intriguing post on a Math Facebook group in 2019, which inspired the journey leading to this article.

Supplementary Materials

References

  1. K. Appel and W. Haken. Every planar map is four colorable. Part I: Discharging. Illinois Journal of Mathematics, 21(3):429-490, 1977. URL: https://doi.org/10.1215/ijm/1256049011.
  2. Armin Biere, Katalin Fazekas, Mathias Fleury, and Maximillian Heisinger. CaDiCaL, Kissat, Paracooba, Plingeling and Treengeling entering the SAT Competition 2020. In Tomas Balyo, Nils Froleyks, Marijn Heule, Markus Iser, Matti Järvisalo, and Martin Suda, editors, Proc. of SAT Competition 2020 - Solver and Benchmark Descriptions, volume B-2020-1 of Department of Computer Science Report Series B, pages 51-53. University of Helsinki, 2020. Google Scholar
  3. Boštjan Brešar, Jasmina Ferme, Sandi Klavžar, and Douglas F. Rall. A survey on packing colorings. Discussiones Mathematicae Graph Theory, 40(4):923, 2020. URL: https://doi.org/10.7151/dmgt.2320.
  4. Shawn T. Brown, Paola Buitrago, Edward Hanna, Sergiu Sanielevici, Robin Scibek, and Nicholas A. Nystrom. Bridges-2: A Platform for Rapidly-Evolving and Data Intensive Research, pages 1-4. Association for Computing Machinery, New York, NY, USA, 2021. Google Scholar
  5. Jan Ekstein, Jirí Fiala, Premysl Holub, and Bernard Lidický. The packing chromatic number of the square lattice is at least 12. CoRR, abs/1003.2291, 2010. URL: http://arxiv.org/abs/1003.2291.
  6. Jiří Fiala and Petr A. Golovach. Complexity of the packing coloring problem for trees. In Hajo Broersma, Thomas Erlebach, Tom Friedetzky, and Daniel Paulusma, editors, Graph-Theoretic Concepts in Computer Science, pages 134-145, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg. Google Scholar
  7. Jiří Fiala, Sandi Klavar, and Bernard Lidický. The packing chromatic number of infinite product graphs. Eur. J. Comb., 30(5):1101-1113, July 2009. URL: https://doi.org/10.1016/j.ejc.2008.09.014.
  8. Wayne Goddard, Sandra Hedetniemi, Stephen Hedetniemi, John Harris, and Douglas Rall. Braodcast chromatic numbers of graphs. Ars Comb., 86, January 2008. Google Scholar
  9. Marijn J. H. Heule, Oliver Kullmann, Siert Wieringa, and Armin Biere. Cube and conquer: Guiding cdcl sat solvers by lookaheads. In Kerstin Eder, João Lourenço, and Onn Shehory, editors, Hardware and Software: Verification and Testing, pages 50-65, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg. Google Scholar
  10. Barnaby Martin, Franco Raimondi, Taolue Chen, and Jos Martin. The packing chromatic number of the infinite square lattice is less than or equal to 16, 2015. URL: http://arxiv.org/abs/1510.02374v1.
  11. Barnaby Martin, Franco Raimondi, Taolue Chen, and Jos Martin. The packing chromatic number of the infinite square lattice is between 13 and 15. Discrete Applied Mathematics, 225:136-142, 2017. URL: https://doi.org/10.1016/j.dam.2017.03.013.
  12. David Neiman, John Mackey, and Marijn Heule. Tighter bounds on directed ramsey number r(7), 2020. URL: http://arxiv.org/abs/2011.00683.
  13. A. Schwenk. private communication with Wayne Goddard., 2002. Google Scholar
  14. Zehui Shao and Aleksander Vesel. Modeling the packing coloring problem of graphs. Applied Mathematical Modelling, 39(13):3588-3595, July 2015. URL: https://doi.org/10.1016/j.apm.2014.11.060.
  15. Christian Sloper. An eccentric coloring of trees. The Australasian Journal of Combinatorics [electronic only], 29, January 2004. Google Scholar
  16. Alexander Soifer. The Hadwiger-Nelson Problem, pages 439-457. Springer International Publishing, Cham, 2016. URL: https://doi.org/10.1007/978-3-319-32162-2_14.
  17. Roman Soukal and Přemysl Holub. A note on packing chromatic number of the square lattice. The Electronic Journal of Combinatorics, 17(1), March 2010. URL: https://doi.org/10.37236/466.
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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