The S S -packing coloring of the infinite diagonal grid with S = ( 1 , 6 , 6 , … ) S=(1,6,6,\ldots)
Teeradej Kittipassorn, Peerawit Suriya · 2025
Read The S S -packing coloring of the infinite diagonal grid with S = ( 1 , 6 , 6 , … ) S=(1,6,6,\ldots) by Teeradej Kittipassorn, Peerawit Suriya (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-16573.txt.
Introduction
Teeradej Kittipassorn and Peerawit Suriya solve a coloring puzzle on an endless grid in a 2025 math paper. The grid is a diagonal one that runs on without bound. Colors must keep same-colored points far apart, with gaps set by a fixed list. The list here starts with a small gap and then repeats a larger one.
The pair prove that the least number of colors needed is forty. Their proof must handle a grid with no edge to lean on. Packing rules like these show up in channel assignment and code design. An exact answer for an endless case is a firm anchor for nearby finite puzzles.
Catalog record
| CREATOR | Teeradej Kittipassorn, Peerawit Suriya |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 63 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-16573
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
The S S -packing coloring of the infinite diagonal grid with S = ( 1 , 6 , 6 , … ) S=(1,6,6,\ldots) Teeradej Kittipassorn, Peerawit Suriya Abstract For a non-decreasing sequence of positive integers S = ( a 1 , a 2 , … ) S=(a_{1},a_{2},\ldots) , the S S -packing chromatic number of a graph G G is the smallest positive integer k k such that the vertices can be colored with k k colors, where the distance between any two distinct vertices of color i i is greater than a i a_{i} . In this paper, we show that the S S -packing chromatic number of the infinite diagonal grid P ∞ ⊠ P ∞ P_{\infty}\boxtimes P_{\infty} with S = ( 1 , 6 , 6 , … ) S=(1,6,6,\ldots) is 40 40 . This confirms a conjecture of the first author and Tiyajamorn. 1 Introduction Graph coloring is one of the most well-known concepts in graph theory with many applications and open problems. A proper coloring of a graph G is an assignment of a color to each vertex such that the distance between any two distinct vertices of the same color is greater than 1 . The minimum number of colors is called the chromatic number of G . A natural question that arises when considering proper coloring is: what is the chromatic number of a given graph G ? For a non-decreasing sequence of positive integers S=(a_{1},a_{2},\ldots) , the S -packing coloring of a graph G is an assignment of a color to each vertex such that the distance between any two distinct vertices of color i is greater than a_{i} . The minimum number of colors is called the S -packing chromatic number , denoted by \chi_{S}(G) . Note that a proper coloring is precisely an S -packing coloring with S=(1,1,\ldots) . In the case S=(1,2,3,\ldots) , this coloring is also known as the packing coloring , with packing chromatic number denoted by \chi_{\rho}(G) . This concept was first studied in 2008 by Goddard, S. M. Hedetniemi, S. T. Hedetniemi, Harris and Roll [ 3 ] . An S -packing coloring has been studied in various types of graphs. Several graphs that have been studied is infinite. The two-way infinite path P_{\infty} is a graph such that V(P_{\infty})=\mathbb{Z} and \{u,v\}\in E(P_{\infty}) if |u-v|=1 . The infinite square grid P_{\infty}\Box P_{\infty} is a graph such that V(P_{\infty}\Box P_{\infty})=\mathbb{Z}\times\mathbb{Z} and \{(x,y),(x^{\prime},y^{\prime})\}\in E(P_{\infty}\Box P_{\infty}) if either x=x^{\prime} and |y-y^{\prime}|=1 , or y=y^{\prime} and |x-x^{\prime}|=1 . The infinite diagonal grid P_{\infty}\boxtimes P_{\infty} is obtained from P_{\infty}\Box P_{\infty} by adding edges \{(x,y),(x^{\prime},y^{\prime})\} if |x-x^{\prime}|=|y-y^{\prime}|=1 . In 2012, Goddard and Xu [ 12 ] studied the two-way infinite path P_{\infty} for many sequences S and obtained exact values and bounds for \chi_{S}(P_{\infty}) . Goddard and Xu [ 4 ] also studied the infinite square grid P_{\infty}\Box P_{\infty} for many sequences in 2014. In the case S=(1,2,3,\ldots) , there have been many results on the infinite square grid since 2008 [ 1 , 2 , 3 , 7 , 8 , 9 , 10 ] , improving the lower and upper bounds for \chi_{\rho}(P_{\infty}\Box P_{\infty}) . In 2023, Subercaseaux and Heule [ 11 ] finally proved that \chi_{\rho}(P_{\infty}\Box P_{\infty})=15 by using a SAT solver. In 2017, Korže and Vesel [ 6 ] studied the case where S is of the form a_{i}=d+\lfloor\tfrac{i-1}{n}\rfloor , where d and n are small positive integers, in the infinite diagonal grid P_{\infty}\boxtimes P_{\infty} . Later, in 2024, the first author and Tiyajamorn [ 5 ] studied S -packing colorings of the infinite diagonal grid with S=(i,k,k,\ldots) . One of the incomplete cases is i=1 with even k . They obtained lower and upper bounds for \chi_{S}(P_{\infty}\boxtimes P_{\infty}) which are \frac{3k^{2}}{4}+\frac{3k}{2}+3\leq\chi_{S}(P_{\infty}\boxtimes P_{\infty})\leq\left\lceil\frac{3k^{2}+7k+8}{4}\right\rceil. For k=2 and k=4 , from the bounds, the exact values of \chi_{S}(P_{\infty}\boxtimes P_{\infty}) are 9 and 21 , respectively. For k=6 , their result implies that 39\leq\chi_{S}(P_{\infty}\boxtimes P_{\infty})\leq 40 . They conjectured that \chi_{S}(P_{\infty}\boxtimes P_{\infty})=40 . In this paper, we confirm the conjecture by showing that it is impossible to use only 39 colors for an S -packing coloring of P_{\infty}\boxtimes P_{\infty} with S=(1,6,6,\ldots) . Theorem 1 . If S=(1,6,6,\ldots) , then \chi_{S}(P_{\infty}\boxtimes P_{\infty})=40 . The rest of the paper is organized as follows. In Section 2 , we make basic observations. We introduce the main Lemma, Lemma 4 , in Section 3 . In Section 4 , we prove Theorem 1 using Observation 2 and Lemma 4 . Lemma 4 is proved in Section 5 . Finally, in Section 6 , we conclude the paper with some open problems. 2 Observations In this section, we explain how we visualize the graph P_{\infty}\boxtimes P_{\infty} and introduce some notations used in this paper. We also provide basic observations along with their proofs. Let S=(1,6,6,6,\ldots) . Throughout this paper we assume that \chi_{S}(P_{\infty}\boxtimes P_{\infty})\leq 39 , since this is the assumption in the proof. That is, there exists an S -packing coloring of P_{\infty}\boxtimes P_{\infty} that uses at most 39 colors. We refer to these colors as colors 1,2,\ldots,39 . From the sequence S , any two vertices of color 1 must have distance greater than 1, while any two vertices of color i\neq 1 must have distance greater than 6. We represent the graph P_{\infty}\boxtimes P_{\infty} using an infinite square grid, where each square corresponds to a vertex of the graph. The distance between any two vertices is defined as the minimum number of steps between corresponding squares, where each step moves one square horizontally, vertically, or diagonally, like a king’s move in chess. Let G be a P_{m}\boxtimes P_{n} subgraph of P_{\infty}\boxtimes P_{\infty} . We refer to each square in G as (x,y) , for 1\leq x\leq m and 1\leq y\leq n , where (1,1) corresponds to the bottom-left corner of G , and (m,n) to the top-right corner. Moreover, we refer to squares (x,j) , for 1\leq x\leq m , as row j , and squares (i,y) , for 1\leq y\leq n , as column i . Sometimes, we may allow x and y to be outside the ranges to refer to a square outside G . We denote by c(G) the number of squares of color 1 in the subgraph G . Observation 2 . (i) If G is a P_{2}\boxtimes P_{2} subgraph, then c(G)\leq 1 . (ii) If G is a P_{7}\boxtimes P_{2} subgraph, then c(G)\leq 4 . Moreover, if c(G)=4 , then the squares of color 1 must lie in columns 1, 3, 5, and 7. (iii) Each P_{7}\boxtimes P_{7} subgraph contains at most one square of color i , for i\in\{2,3,\ldots,39\} . (iv) If G is a P_{7}\boxtimes P_{7} subgraph, then c(G)\geq 11 . Moreover, if c(G)=11 , then all colors 1,2,\ldots,39 must appear in G . Proof. (i) Since the distance between any two squares of color i must be at least 2, and the distance between any two squares in P_{2}\boxtimes P_{2} is equal to 1 , we have c(G)\leq 1 . (ii) We partition G into four parts, as shown in Figure 1 . By Observation 2 (i), we have c(G)\leq 4 . Moreover, if c(G)=4 , it follows that each part must contain exactly