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

DOI10.1016/j.dam.2017.03.013zbMath1361.05051arXiv1510.02374OpenAlexW2590872906MaRDI QIDQ528575

Barnaby Martin, Jos Martin, Franco Raimondi, Taolue Chen

Publication date: 12 May 2017

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

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

zbMATH Keywords

graph colouringSAT solvingpacking chromatic numberbroadcast chromatic number

Mathematics Subject Classification ID

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

Related Items (16)

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

Cites Work

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

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