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

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

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: Apr 17, 2018
• Journal: Discrete Applied Mathematics
• Print ISSN: 0166-218X
• Electronic ISSN: 1872-6771
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 225
• Pages: 136-142
• DOI: https://doi.org/10.1016/j.dam.2017.03.013
• Public URL: https://durham-repository.worktribe.com/output/1349779