Publication details for Dr Barnaby MartinMartin, Barnaby, Raimondi, Franco, Chen, Taolue & Martin, Jos (2017). The packing chromatic number of the infinite square lattice is between 13 and 15. Discrete Applied Mathematics 225: 136-142.
- Publication type: Journal Article
- ISSN/ISBN: 0166-218X (print)
- DOI: 10.1016/j.dam.2017.03.013
- Further publication details on publisher web site
- Durham Research Online (DRO) - may include full text
Author(s) from Durham
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.