Cookies

We use cookies to ensure that we give you the best experience on our website. You can change your cookie settings at any time. Otherwise, we'll assume you're OK to continue.

Durham University

Research & business

View Profile

Publication details for Dr Barnaby Martin

Martin, 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.

Author(s) from Durham

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.