Skip to main content

Research Repository

Advanced Search

The packing chromatic number of the infinite square lattice is between 13 and 15

Martin, Barnaby; Raimondi, Franco; Chen, Taolue; Martin, Jos

The packing chromatic number of the infinite square lattice is between 13 and 15 Thumbnail


Authors

Franco Raimondi

Taolue Chen



Abstract

Using a SAT-solver on top of a partial previously-known solution we improve the upper bound of the packing chromatic number of the infinite square lattice from 17 to 15. We discuss the merits of SAT-solving for this kind of problem as well as compare the performance of different encodings. Further, we improve the lower bound from 12 to 13 again using a SAT-solver, demonstrating the versatility of this technology for our approach.

Citation

Martin, B., Raimondi, F., Chen, T., & Martin, J. (2017). The packing chromatic number of the infinite square lattice is between 13 and 15. Discrete Applied Mathematics, 225, 136-142. https://doi.org/10.1016/j.dam.2017.03.013

Journal Article Type Article
Acceptance Date Mar 27, 2017
Online Publication Date Apr 17, 2017
Publication Date Apr 17, 2017
Deposit Date Sep 8, 2017
Publicly Available Date Mar 29, 2024
Journal Discrete Applied Mathematics
Print ISSN 0166-218X
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 225
Pages 136-142
DOI https://doi.org/10.1016/j.dam.2017.03.013

Files





You might also like



Downloadable Citations