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

2025/09/20 by Teeradej Kittipassorn, Kittipassorn, Teeradej, Peerawit Suriya +1
Computer Science · Engineering · #05C15 (Primary) 05C35 (Secondary) #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #Digital Image Processing Techniques #FOS: Mathematics #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.2509.16573

openalex publication_date 2025/09/20 · openalex created_date 2025/10/16 · openalex updated_date 2026/07/28

Abstract

For a non-decreasing sequence of positive integers S = (a₁, a₂,…), the S-packing chromatic number of a graph G is the smallest positive integer k such that the vertices can be colored with k colors, where the distance between any two distinct vertices of color i is greater than a_i. In this paper, we show that the S-packing chromatic number of the infinite diagonal grid P_∞ \boxtimes P_∞ with S = (1,6,6,…) is 40. This confirms a conjecture of the first author and Tiyajamorn.

Citations

• The Packing Chromatic Number of the Infinite Square Grid is 15
• The packing chromatic number of the infinite square lattice is between\n 13 and 15
• The packing chromatic number of the square lattice is at least 12

Related

• The Packing Chromatic Number of the Infinite Square Grid is 15
• Subdivision into i-packings and S-packing chromatic number of some lattices
• S-packing colorings of distance graphs G(ℤ,\2,t\)
• The Packing Coloring of Distance Graphs D(k,t)
• S-packing colorings of distance graphs with distance sets of cardinality 2