The packing chromatic number of the infinite square grid is 15

DOI10.1007/978-3-031-30823-9_20MaRDI QIDQ6535369zbMATH OpenFDO

Authors Bernardo Subercaseaux, Marijn J. H. Heule

Publication date 13 December 2023

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/978-3-031-30823-9_20

zbMATH Keywords

packing coloringSATverification

Mathematics Subject Classification ID

Distance in graphs (05C12) Coloring of graphs and hypergraphs (05C15) Computational aspects of satisfiability (68R07)

Recommendations

• The packing chromatic number of the infinite square lattice is between 13 and 15
• 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
• (d, n)-packing colorings of infinite lattices

Cites work

• A note on packing chromatic number of the square lattice
• A survey on packing colorings
• A survey on the distance-colouring of graphs
• Broadcast chromatic numbers of graphs
• DRAT proofs, propagation redundancy, and extended resolution
• Every planar map is four colorable. I: Discharging
• On a generalization of extended resolution
• On the packing chromatic number of some lattices
• The Hadwiger-Nelson problem
• The packing chromatic number of infinite product graphs
• The packing chromatic number of the infinite square grid is at least 14
• The packing chromatic number of the infinite square lattice is between 13 and 15
• Tighter bounds on directed Ramsey number \(R(7)\)
• What a difference a variable makes

Cited in

(11)

• On uniquely packable trees
• Packing coloring of hypercubes with extended Hamming codes
• Partial packing coloring and quasi-packing coloring of the triangular grid
• Formal verification of the empty hexagon number
• Artificial intelligence and inherent mathematical difficulty
• Producing proofs of unsatisfiability with distributed clause-sharing SAT solvers
• Distance dominator packing coloring of type II
• Sometimes hoarding is harder than cleaning: NP-hardness of maximum blocked-clause addition
• Toward optimal radio colorings of hypercubes via SAT-solving
• On the packing chromatic numbers of four and five regular connected spanning subgraphs of \(\mathbb{Z}^3\)
• North-east lattice paths avoiding k collinear points via satisfiability

This page was built for publication: The packing chromatic number of the infinite square grid is 15

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