Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

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

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:
Export
Look up in GoogleScholar