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

2015/10/08 by Barnaby Martin, Franco Raimondi, Martin, Barnaby +5 · 2 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · Engineering · #Combinatorics (math.CO) #DNA and Biological Computing #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #graph theory and CDMA systems #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1510.02374

openalex publication_date 2015/10/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Using a SAT-solver on top of a partial previously-known solution we improve\nthe upper bound of the packing chromatic number of the infinite square lattice\nfrom 17 to 15. We discuss the merits of SAT-solving for this kind of problem as\nwell as compare the performance of different encodings. Further, we improve the\nlower bound from 12 to 13 again using a SAT-solver, demonstrating the\nversatility of this technology for our approach.\n

Cited by

• The S-packing coloring of the infinite diagonal grid with S = (1,6,6,…)
• On Sierpiński packing chromatic number and recognition of Sierpiński products

Related

• The Packing Chromatic Number of the Infinite Square Grid is 15
• The packing chromatic number of the square lattice is at least 12
• Subdivision into i-packings and S-packing chromatic number of some lattices
• On SAT Solvers and Ramsey-type Numbers
• Packing, Hitting, and Colouring Squares