The packing chromatic number of the square lattice is at least 12

2010/03/11 by Jan Ekstein, Ekstein, Jan, Jiří Fiala +5 · 1 citation
Computer Science · #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #G.2.2 #cs.DM

paper · pdf · doi:10.48550/arxiv.1003.2291

3 pages

arxiv created 2010/03/11 · arxiv updated 2010/03/12

Abstract

The packing chromatic number χ_ρ(G) of a graph G is the smallest integer k such that the vertex set V(G) can be partitioned into disjoint classes X₁, ..., X_k, where vertices in X_i have pairwise distance greater than i. For the 2-dimensional square lattice ℤ² it is proved that χ_ρ(ℤ²) ≥ 12, which improves the previously known lower bound 10.

Cited by

• The S-packing coloring of the infinite diagonal grid with S = (1,6,6,…)

Related

• Packing chromatic number under local changes in a graph
• Packing Chromatic Number of Distance Graphs
• Subdivision into i-packings and S-packing chromatic number of some lattices
• Packing colouring of some classes of cubic graphs
• Packing chromatic number of subdivisions of cubic graphs