Martin, Barnaby and Raimondi, Franco and Chen, Taolue and Martin, Jos (2017) 'The packing chromatic number of the infinite square lattice is between 13 and 15.', Discrete applied mathematics., 225 . pp. 136-142.
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.
| Item Type: | Article |
|---|---|
| Full text: | (AM) Accepted Manuscript Available under License - Creative Commons Attribution Non-commercial No Derivatives. Download PDF (261Kb) |
| Status: | Peer-reviewed |
| Publisher Web site: | https://doi.org/10.1016/j.dam.2017.03.013 |
| Publisher statement: | © 2017 This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/ |
| Date accepted: | 27 March 2017 |
| Date deposited: | 12 September 2017 |
| Date of first online publication: | 17 April 2017 |
| Date first made open access: | 17 April 2018 |
Save or Share this output
| Export: | |
| Look up in GoogleScholar |
