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

DOI10.1016/J.DAM.2017.03.013zbMATH Open1361.05051arXiv1510.02374OpenAlexW2590872906MaRDI QIDQ528575FDOQ528575

Authors: Barnaby Martin, Franco Raimondi, Taolue Chen, Jos Martin 

Publication date: 12 May 2017

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1510.02374

Recommendations

• On the packing chromatic number of square and hexagonal lattice
• A note on packing chromatic number of the square lattice
• The packing chromatic number of infinite product graphs
• On the packing chromatic number of Cartesian products, hexagonal lattice, and trees
• On the packing chromatic number of Cartesian products, hexagonal lattice, and trees

zbMATH Keywords

graph colouringSAT solvingpacking chromatic numberbroadcast chromatic number

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• A note on packing chromatic number of the square lattice
• A note on \(S\)-packing colorings of lattices
• Broadcast chromatic numbers of graphs
• On the packing chromatic number of Cartesian products, hexagonal lattice, and trees
• Complexity of the packing coloring problem for trees
• On the packing chromatic number of some lattices
• A new method to construct lower bounds for van der Waerden numbers
• Satisfiability and computing van der Waerden numbers
• A SAT Attack on the Erdős Discrepancy Conjecture
• A lower bound for the packing chromatic number of the Cartesian product of cycles
• Modeling the packing coloring problem of graphs
• Subdivision into i-packings and S-packing chromatic number of some lattices
• Packing chromatic number, \((1, 1, 2, 2)\)-colorings, and characterizing the Petersen graph
• Bridging constraint satisfaction and Boolean satisfiability

Cited In (19)

• A GENERAL POSITION PROBLEM IN GRAPH THEORY
• A heuristic approach for searching \((d, n)\)-packing colorings of infinite lattices
• On the packing chromatic number of Moore graphs
• Notes on complexity of packing coloring
• An infinite family of subcubic graphs with unbounded packing chromatic number
• Packing chromatic number versus chromatic and clique number
• \((d, n)\)-packing colorings of infinite lattices
• A survey on packing colorings
• \(S\)-packing colorings of distance graphs \(G ( \mathbb{Z} , \{ 2 , t \} )\)
• Packing chromatic number of windmill related graphs and chain silicate networks
• Graphs that are critical for the packing chromatic number
• Independence number and packing coloring of generalized Mycielski graphs
• Packing coloring of Sierpiński-type graphs
• Partial packing coloring and quasi-packing coloring of the triangular grid
• Packing colorings of subcubic outerplanar graphs
• On the packing chromatic number of subcubic outerplanar graphs
• \(S\)-packing chromatic vertex-critical graphs
• The packing chromatic number of the infinite square grid is 15
• Packing chromatic numbers of finite super subdivisions of graphs

This page was built for publication: The packing chromatic number of the infinite square lattice is between 13 and 15

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q528575)