An S-packing k-coloring of a graph \(G\) (with \(S=(s_1,s_2,\dots)\) is a non-decreasing sequence of positive integers) is a mapping \(f\) from \(V(G)\) to \(\lbrace 1,\dots , k \rbrace\) (the set of colors) such that for every two distincts vertices \(x\) and \(y\) in \(V(G)\) with \(f(x)=f(y)=i\) the distance between \(x\) and \(y\) in \(G\) is bigger than \(s_i\). The S-packing chromatic number \(\chi_S (G)\) of \(G\) is the smallest integer \(k\) such that \(G\) has an S-packing k-coloring. Given a set \(D\subset \mathbb{N}^*\), a distance graph \(G(\mathbb{Z}, D)\) with distance set \(D\) is a graph with vertex set \(\mathbb{Z}\) and two distincts vertices \(u\) and \(v\) are adjacents if \(| u-v | \in D\). In this paper, for \(S=(s,s+1,s+1,\dots)\) with \(s \geq \left\lceil \frac{t}{2} \right\rceil\) we give a lower bound of \(\chi_S (G(\mathbb{Z}, \lbrace 1, t\rbrace))\), and a lower bound of \(\chi_d (G(\mathbb{Z}, \lbrace 1, t\rbrace))\) with \(d \geq \left\lceil \frac{t}{2} \right\rceil\), for \(S=(s_1,s_2,\dots, s_i,a,a,\dots)\) with \(a \geq \max( 1 , t-2 )\) we give an upper bound of \(\chi_S (G(\mathbb{Z}, \lbrace 1, t\rbrace))\), and we determine the exact values of \(\chi_S (G(\mathbb{Z}, \lbrace 1, t\rbrace))\) and also of \(\chi_d (G(\mathbb{Z}, \lbrace 1, t\rbrace))\) for \(s\geq \max (\left\lceil \frac{t}{2} \right\rceil, t-3)\) and \(d \geq \max (\left\lceil \frac{t}{2} \right\rceil , t-2)\). And we give a lower and an upper bound of \(\chi_S (G(\mathbb{Z}, \lbrace 1, t\rbrace))\) for \(S=(1,s,s,\dots)\) with conditions on \(s\) and \(t\), which in the cases \(s\geq \max (t-2,\left\lceil \frac{t}{2}\right\rceil)\) we determine the exact values of \(\chi_S (G(\mathbb{Z}, \lbrace 1, t\rbrace))\).
Goddard, Hedetniemi, Hedetniemi, Harris, and Rall are the first researchers who introduced the concept of S-packing [7], under the name broadcast coloring. This concept was introduced to generalize the notion of a proper coloring and came about as a result of potential applications in problem of distributing broadcast frequencies to radio stations. There are several domains for the applications of S-packing coloring [3]. The S-packing chromatic number (with \(S=(s_1,s_2,\dots)\) is a non-decreasing sequence of positive integers) of a graph \(G\) is the smallest number of the colors such that the distance between two vertices have the same color \(i\) is bigger than \(s_i\).
In this paper, we are studying the undirected simple graphs only. Let \(G\) be a graph, we denote by \(V(G)\) the set of vertices of G, and we call the distance between two vertices \(u\) and \(v\) of \(V(G)\) the length of a shortest path between u and v in G, denoted by \(d_G(u,v)\). Let \(S=(s_1,s_2,\dots)\) be a non-decreasing sequence of positive integers, a mapping \(f:V(G) \rightarrow \lbrace 1,\dots , k \rbrace\) with \(k\in \mathbb{N}^*\) called S-packing k-coloring of \(G\) if for all differents vertices \(u\) and \(v\) belongs to \(V(G)\) with \(f(u)=f(v)=i\) the distance between \(u\) and \(v\) is bigger than \(s_i\). The smallest integer \(k\) such that \(G\) admits an S-packing k-coloring is called the S-packing chromatic number of \(G\), and we note it \(\chi_S (G)\). for \(S=(1,1,1,\dots)\) it’s about the proper coloring and the chromatic number of \(G\) denoted by \(\chi(G)\), for \(S=(d,d,d,\dots)\) with \(d\in \mathbb{N}\) it’s about the d-distance coloring and the d-distance chromatic number of \(G\) denoted by \(\chi_d (G)\), if \(S=(1,2,3,\dots)\) yields the packing coloring and the packing chromatic number of \(G\) denoted by \(\chi_{\rho} (G)\).
Let \(D\subset \mathbb{N}^*\). A distance graph \(G(\mathbb{Z}, D)\) with distance set \(D\) is the graph with \(\mathbb{Z}\) as the vertex set, and two vertices \(x\) and \(y\) are adjacent if and only if \(| x-y | \in D\), for simplification, \(G(\mathbb{Z}, \lbrace d_1,d_2,\dots,d_k \rbrace)\) be noted \(D(d_1,d_2,\dots,d_k)\).
Holub and Hofman studied the S-packing colorings of the distance graphs \(D(1,t)\) and \(D(1,2,t)\) for \(S\) having all elements from \(\lbrace 1,2 \rbrace\) [9]. Benmedjdoub et al. [1] investigated the 2-distance chromatic number of integer distance graphs for several types of sets \(D\). Distance graphs were first studied systematically by Eggleton et al. in [8]. There exist many results about S-packing chromatic number of distance graphs, see [1, 2, 4, 5, 6, 10, 9, 11], but most results concern small-valued sequences. This motivates our focus here on the higher-valued sequences \((1,s,s,\ldots)\) and \((s,s+1,s+1,\ldots)\) with \(s\ge \left\lceil \frac{t}{2}\right\rceil\).
In this paper, we are studying the S-packing chromatic number and the d-distance chromatic number of graph \(D(1,t)\) with \(t>1\) for \(S=(s,s+1,s+1,\dots)\) and for \(S=(1,s,s,\dots)\) with \(s\geq \left\lceil \frac{t}{2} \right\rceil\) and \(d \geq \left\lceil \frac{t}{2} \right\rceil\).
For integers \(x\leq y\), let \(⟦ x, y ⟧ = \lbrace x,x+1,…,y \rbrace\) (in particular, \(⟦ x, x ⟧ = \lbrace x \rbrace\)).
We begin by recalling a fundamental distance formula for \(D(1,t)\), established by Togni [11].
Lemma 2.1. [11] The distance between two vertices \(u\) and \(v\) of \(D(1,t)\) is \(d_{D(1,t)}(u,v)=\min (q+r,q+1+t-r)\), where \(| u-v |= qt+r\) with \(0 \leq r < t\).
We also recall the following observation, due to Goddard and Xu [8].
Observation 2.2. [8] If \(G_2\) is a subgraph of \(G_1\), then \(\chi _S (G_2)\leq \chi _S (G_1)\) for every sequence \(S\).
Lemma 2.3. Let \(t>1\) be an integer and \(s\geq \left\lceil \frac{t}{2} \right\rceil\) be an integer. Let \(u\) and \(v\) two vertices of \(D(1,t)\). If \(d_{D(1,t)}(u,v)> s\), then \(\left\lvert v-u\right\rvert \geq t(s-\left\lceil \frac{t}{2}\right\rceil+1)+\left\lceil \frac{t}{2}\right\rceil\).
Proof. Suppose that \(d_{D(1,t)}(u,v)> s\). Let \(\left\lvert v-u\right\rvert = qt + r\) where \(q,r\in \mathbb{N}\) and \(0 \leq r<t\). By Lemma 2.1, \(\min (q+r,q+1+t-r)=d_{D(1,t)}(u,v)> s\), then \(q+r>s\) and \(q+1+t-r>s\), it follows that \(q\geq s+\frac{1}{2}-\frac{t}{2}\). Hence \(q\geq s+1-\left\lceil \frac{t}{2} \right\rceil\). If \(q> s+1-\left\lceil \frac{t}{2} \right\rceil\), then \(\left\lvert v-u\right\rvert \geq t(s-\left\lceil \frac{t}{2}\right\rceil+1)+\left\lceil \frac{t}{2}\right\rceil\). If \(q= s+1-\left\lceil \frac{t}{2} \right\rceil\), we have \(r>s-q\geq \left\lceil \frac{t}{2} \right\rceil -1\), implies that \(\left\lvert v-u\right\rvert \geq t(s-\left\lceil \frac{t}{2}\right\rceil+1)+\left\lceil \frac{t}{2}\right\rceil\). Therefore we obtain the result. ◻
The previous lemma implies that if \(s_i\ge \left\lceil \frac{t}{2}\right\rceil\), then any two vertices of \(D(1,t)\) colored by color \(i\) in an \(S\)-packing coloring must be at least \[L_i \;:=\; t\!\left(s_i-\left\lceil\frac{t}{2}\right\rceil+1\right)+\left\lceil\frac{t}{2}\right\rceil,\] apart on the integer line. In particular, any integer interval of size at most \(L_i\) contains at most one vertex of color \(i\).
Lemma 2.4. Let \(S=(s_1,s_2,\dots)\) be a non-decreasing sequence of positive integers. Let \(H\) be a subgraph of \(D(1,t)\) with vertex set \(X=⟦ a, b ⟧ \subset \mathbb{Z}\), let \(f\) be an S-packing k-coloring of subgraph \(H\) from \(X\) to \(⟦ 1,k ⟧\) with \(k\in \mathbb{N}^*\). Suppose that there exists \(i\in ⟦ 1,k ⟧\) such that \(s_i\geq \left\lceil \frac{t}{2} \right\rceil\), then \[\bigl| \lbrace x\in X: f(x)=i \rbrace \bigr| \leq q +\min \lbrace 1,r\rbrace ,\] where \(\left\lvert X \right\rvert= \left( t(s_i-\left\lceil \frac{t}{2}\right\rceil+1)+\left\lceil \frac{t}{2}\right\rceil \right) q +r\) with \(q,r\in \mathbb{N}\) and \(0 \leq r < t(s_i-\left\lceil \frac{t}{2}\right\rceil+1)+\left\lceil \frac{t}{2}\right\rceil\).
Proof. We prove that \(\bigl| \lbrace x\in X: f(x)=i \rbrace \bigr| \leq q +\min \lbrace 1,r\rbrace\). Suppose to the contrary that \(\bigl| \lbrace x\in X: f(x)=i \rbrace \bigr| \geq q +\min \lbrace 1,r\rbrace +1\).
Set \(X'=\lbrace x\in X: f(x)=i \rbrace\) and \(m=\left\lvert X' \right\rvert\). Let \(x_1 < x_2 < \dots < ~x_{m}\) be the elements of \(X'\). Since \(f(x_1)=f(x_2)=\dots =f(x_m)=i\), it follows that \(d_{D(1,t)}(x_n,x_{n+1})> s_i\) for all \(n \in ⟦ 1,m ⟧\). Hence, by Lemma 2.3, we have \(x_{n+1}-x_n \geq t(s_i-\left\lceil \frac{t}{2}\right\rceil+1)+\left\lceil \frac{t}{2}\right\rceil\) for all \(n \in ⟦ 1,m ⟧\), which implies \(x_{m}-x_1 \geq (m-1)\left( t(s_i-\left\lceil \frac{t}{2}\right\rceil+1)+\left\lceil \frac{t}{2}\right\rceil \right)\).
Thus \(b-a\geq x_{m}-x_1\geq (q +\min \lbrace 1,r\rbrace)\left( t(s_i-\left\lceil \frac{t}{2}\right\rceil+1)+\left\lceil \frac{t}{2}\right\rceil \right)\), a contradiction since \(b-a+1=\left\lvert X\right\rvert < (q +\min \lbrace 1,r\rbrace)\left( t(s_i-\left\lceil \frac{t}{2}\right\rceil+1)+\left\lceil \frac{t}{2}\right\rceil \right) +1\). ◻
Lemma 2.5. Let \(t> 1\) be an integer and \(a\geq t-1\) be an integer, and let \(l\in \mathbb{N}^*\). Then \(d_{D(1,t)}(0,lt(a-\left\lceil \frac{t}{2}\right\rceil)+l\left\lceil \frac{t}{2}\right\rceil ) \geq a\).
Proof. Let \(lt(a-\left\lceil \frac{t}{2}\right\rceil)+l\left\lceil \frac{t}{2}\right\rceil= qt+r\) with \(r,q\in\mathbb{N}\) and \(0\leq r<t\).
If \(l=1\), then \(q=a-\left\lceil \frac{t}{2}\right\rceil\) and \(r=\left\lceil \frac{t}{2}\right\rceil\). Thus \[d_{D(1,t)}\left(0,t\left(a-\left\lceil \frac{t}{2}\right\rceil\right)+\left\lceil \frac{t}{2}\right\rceil \right)=\min(q+r,q+1+t-r) \geq a.\]
Otherwise, since \(l\left\lceil \frac{t}{2}\right\rceil\geq t\), \(q> l(a-\left\lceil \frac{t}{2}\right\rceil)\). It follows that \[q+r\geq l\left(a-\left\lceil \frac{t}{2}\right\rceil\right)+1\geq a+t-2\left\lceil \frac{t}{2}\right\rceil \geq a\; and\; q+1+t-r>q+1\geq a.\]
Hence \(d_{D(1,t)}\left(0,lt\left(a-\left\lceil \frac{t}{2}\right\rceil\right)+l\left\lceil \frac{t}{2}\right\rceil \right)=\min(q+r,q+1+t-r) \geq a\). ◻
This lemma shows that if the difference between two vertices of \(D(1,t)\) is exactly \[lt\left(a-\left\lceil \tfrac{t}{2}\right\rceil\right) + l\left\lceil \tfrac{t}{2}\right\rceil,\] then, provided that \(a \ge t-1\), their distance in \(D(1,t)\) is at least \(a\).
In this section we study \((s,s+1,s+1,\dots)\)–packing colorings of the distance graphs \(D(1,t)\) for \(s\geq \left\lceil \frac{t}{2}\right\rceil\). To the best of our knowledge, this family has not been studied systematically; previous studies have focused on other sequences with smaller distance requirements, most notably \((1,2,2,\dots)\) on \(D(1,t)\) (see Holub and Hofman [9]). As a preliminary step, we establish a general upper bound for eventually constant sequences.
Theorem 3.1. Let \(t>1\) be an integer, \(a\geq \max(1,t-2)\) be an integer and \(s_1,s_2,\dots,s_i\) be integers with \(1 \leq s_1\leq s_2 \leq \dots \leq s_i \leq a\), and let \(S=(s_1,s_2,\dots,s_i,a,a,\dots)\). Then \(\chi_{S} (D(1,t))\leq t\left(a+1-\left\lceil \frac{t}{2}\right\rceil\right)+\left\lceil \frac{t}{2}\right\rceil\).
Proof. We set \(k=t\left(a+1-\left\lceil \frac{t}{2}\right\rceil\right)+\left\lceil \frac{t}{2}\right\rceil\) and \(J= ⟦ 1, k⟧\). Define \(f:\mathbb{Z}\to J\) by: \(f(u)=j \quad\text{where } u \equiv j-1 \pmod{k}\) and \(j\in J\).
It is clear that \(f\) is well defined. Let \(u\) and \(v\) be two vertices of \(\mathbb{Z}\) with \(u<v\) such that \(f(u)=f(v)=j\) with \(j\in J\), then there exists \(l,l'\in \mathbb{Z}\) such that \(u=lk+j-1\) and \(v=l' k+j-1\), which implies \(v-u=(l'-l)k\). It follows that \(d_{D(1,t)}(u,v)=d_{D(1,t)}(0,(l'-l)k)\). Since \(l'-l \in \mathbb{N}^*\) and \(a+1 \geq t-1\), hence, by Lemma 2.5, we have \(d_{D(1,t)}(0,(l'-l)k) \geq a+1\), then \(d_{D(1,t)}(u,v )\geq a+1\).
Thus any two vertices of the same color are at distance at least \(a+1\), and since every \(s_i\le a\), the S-packing constraints are satisfied. Therefore \(f\) is an S-packing k-coloring of \(D(1,t)\), which yields the claimed bound. ◻
We now derive a lower bound for \(\chi_{S}(D(1,t))\) when \(S=(s,s+1,s+1,\dots)\) and \(s\geq \left\lceil \frac{t}{2}\right\rceil\).
Theorem 3.2. Let \(t>1\) be an integer and \(s\geq \left\lceil \frac{t}{2}\right\rceil\) be an integer, and let \(S=(s,s+1,s+1,\dots)\). Then \(\chi_{S} (D(1,t))\geq t\left(s+2-\left\lceil \frac{t}{2}\right\rceil\right)+\left\lceil \frac{t}{2}\right\rceil\).
Proof. We prove that \(\chi_{S} (D(1,t))\geq t\left(s+2-\left\lceil \frac{t}{2}\right\rceil\right)+\left\lceil \frac{t}{2}\right\rceil\).
Case 1. \(s=\left\lceil \frac{t}{2}\right\rceil\). Let \(V=⟦ 0, 2t+3\left\lceil \frac{t}{2}\right\rceil ⟧\). Let \(H\) be a subgraph of \(D(1,t)\) with vertex set \(V\), let \(f\) be an S-packing k-coloring of subgraph \(H\) from \(V\) to \(\lbrace 1,2,\dots,k \rbrace\) with \(k\in \mathbb{N}^*\setminus \lbrace 1\rbrace\), let \(J'=⟦ 1, k ⟧\), \(J=J'\setminus \lbrace 1 \rbrace\), \(V_j=\lbrace i\in V :\; f(i)=j \rbrace\) where \(j\in J'\), and let \(\alpha =\left\lvert V_1\right\rvert\).
By Lemma 2.4, for all \(j\in J\), \(\left\lvert V_j \right\rvert\leq 2\). Let \(\beta =\bigl| \lbrace j\in J :\; \left\lvert V_j \right\rvert =2 \rbrace \bigr|\).
First we claim that \(\beta \leq 2\left\lceil \frac{t}{2}\right\rceil -\alpha +2\). Suppose to the contrary that \(\beta > 2 \left\lceil \frac{t}{2}\right\rceil -\alpha +2\). Since for all \(j_0 \in \lbrace j\in J :\; \left\lvert V_j\right\rvert =2 \rbrace\), there exist \(u\) and \(v\) in \(V\) such that \(u<v\) and \(f(u)=f(v)=j_0>1\), then by Lemma 2.3, \(v-u \geq 2t+\left\lceil \frac{t}{2}\right\rceil\), imply that \(u\in ⟦ 0, 2\left\lceil \frac{t}{2}\right\rceil ⟧\) and \(v \in ⟦ 2t+\left\lceil \frac{t}{2}\right\rceil, 2t+3\left\lceil \frac{t}{2}\right\rceil ⟧\). Hence there exist \(\beta\) vertices in \(⟦ 0, 2\left\lceil \frac{t}{2}\right\rceil ⟧\) and \(\beta\) vertices in \(⟦ 2t+\left\lceil \frac{t}{2}\right\rceil, 2t+3\left\lceil \frac{t}{2}\right\rceil ⟧\) whose colors are each used exactly twice in \(H\), this implies that \(\beta \leq \bigl| ⟦ 0, 2\left\lceil \frac{t}{2}\right\rceil ⟧ \bigr| =2\left\lceil \frac{t}{2}\right\rceil+1\).
By Lemma 2.4, three vertices in \(V\) can be colored with color \(1\). Then \(1\leq \alpha \leq 3\).
Case 1.1. \(\alpha =1\).
We have \(\beta \leq 2\left\lceil \frac{t}{2}\right\rceil+1= 2\left\lceil \frac{t}{2}\right\rceil-\alpha +2\), a contradiction since \(\beta > 2 \left\lceil \frac{t}{2}\right\rceil -\alpha +2\).
Case 1.2. \(\alpha =2\).
Then there exist two vertices \(u_0\) and \(u_0 ^{'}\) in \(V\) such that \(u_0 < u_0 ^{'}\) and \(f(u_0)=f(u_0 ^{'})=1\). Then \(d_{D(1,t)} (u_0,u_0 ^{'})\geq s+1\). Hence by Lemma 2.3, we have \(u_0 ^{'}-u_0 \geq t+\left\lceil \frac{t}{2}\right\rceil\), which implies \(u_0 \in ⟦ 0,t+2 \left\lceil \frac{t}{2}\right\rceil ⟧\) and \(u_0 ^{'} \in ⟦ t+\left\lceil \frac{t}{2}\right\rceil +u_0, 2t+3\left\lceil \frac{t}{2}\right\rceil ⟧\).
If \(u_0 \in ⟦ 0, 2\left\lceil \frac{t}{2}\right\rceil ⟧\), then \(⟦ 0, 2\left\lceil \frac{t}{2}\right\rceil ⟧\) contains a vertex colored with color \(1\), and \(⟦ 0, 2\left\lceil \frac{t}{2}\right\rceil ⟧\) also contains \(\beta\) vertices colored with colors from \(\lbrace j\in J :\; \left\lvert V_j \right\rvert =2 \rbrace\). This implies \(\beta +1\leq \bigl| ⟦ 0, 2\left\lceil \frac{t}{2}\right\rceil ⟧ \bigr|=2\left\lceil \frac{t}{2}\right\rceil+1\), a contradiction since \(\beta > 2 \left\lceil \frac{t}{2}\right\rceil -\alpha +2= 2 \left\lceil \frac{t}{2}\right\rceil\).
If \(u_0 \in ⟦ 2\left\lceil \frac{t}{2}\right\rceil , t+2 \left\lceil \frac{t}{2}\right\rceil⟧\), then \(u_0 ^{'} \in ⟦ t+3\left\lceil \frac{t}{2}\right\rceil , 2t+3\left\lceil \frac{t}{2}\right\rceil ⟧\). Hence \(⟦ t+3\left\lceil \frac{t}{2}\right\rceil , 2t+3\left\lceil \frac{t}{2}\right\rceil ⟧\) contains a vertex of color \(1\) and \(\beta\) other vertices colored with colors from \(\lbrace j\in J :\; \left\lvert V_j \right\rvert =2 \rbrace\). This implies \(\beta +1\leq \bigl| ⟦ 0, 2\left\lceil \frac{t}{2}\right\rceil ⟧ \bigr| =2\left\lceil \frac{t}{2}\right\rceil+1\), a contradiction since \(\beta > 2 \left\lceil \frac{t}{2}\right\rceil\).
Case 1.3. \(\alpha =3\).
Then there exist three vertices \(u_0\), \(u_0 ^{'}\) and \(u_0 ^{''}\) in \(V\) such that \(u_0 < u_0 ^{'} < u_0 ^{''}\) and \(f(u_0)=f(u_0 ^{'})=f(u_0 ^{''})=1\). Then \(d_{D(1,t)} (u_0,u_0 ^{'})\geq s+1\) and \(d_{D(1,t)} (u_0 ^{'},u_0 ^{''})\geq s+1\). Hence by Lemma 2.3, we have \(u_0 ^{'}-u_0 \geq t+\left\lceil \frac{t}{2}\right\rceil\) and \(u_0 ^{''}-u_0 ^{'} \geq t+\left\lceil \frac{t}{2}\right\rceil\), which implies that \(u_0 ^{''}-u_0 \geq 2t+2\left\lceil \frac{t}{2}\right\rceil\). Therefore \(u_0 \in ⟦ 0, \left\lceil \frac{t}{2}\right\rceil ⟧\) and \(u_0 ^{''} \in ⟦ 2t+2\left\lceil \frac{t}{2}\right\rceil, 2t+3\left\lceil \frac{t}{2}\right\rceil ⟧\).
It follows that \(⟦ 0, 2\left\lceil \frac{t}{2}\right\rceil ⟧\) contains a vertex colored with color \(1\), and \(⟦ 0, 2\left\lceil \frac{t}{2}\right\rceil ⟧\) also contains \(\beta\) vertices colored with colors from \(\lbrace j\in J :\; \left\lvert V_j \right\rvert =2 \rbrace\). This implies \(\beta +1\leq \bigl| ⟦ 0, 2\left\lceil \frac{t}{2}\right\rceil ⟧ \bigr| =2\left\lceil \frac{t}{2}\right\rceil+1\). Since \(\beta > 2 \left\lceil \frac{t}{2}\right\rceil -\alpha +2\), we deduce that \(\beta = 2 \left\lceil \frac{t}{2}\right\rceil\).
Let \(j\in \lbrace j\in J :\; \left\lvert V_j \right\rvert =2 \rbrace\). Since \(\left\lvert V_j\right\rvert =2\), there exists \(u_j\) and \(u_j ^{'}\) in \(V\) such that \(u_j < u_j ^{'}\) and \(f(u_j)=f(u_j ^{'})=j>1\), then \(u_j ^{'}\geq 2t+\left\lceil \frac{t}{2}\right\rceil +u_j\). Since \(u_0 ^{''}> 2t+\left\lceil \frac{t}{2}\right\rceil +u_0\), and for all \(u_{j'}\in ⟦ u_0+1, 2\left\lceil \frac{t}{2}\right\rceil ⟧\) with \(j' \in \lbrace j\in J :\; \left\lvert V_j \right\rvert =2 \rbrace\), we have \(u_{j'}^{'}\geq 2t+\left\lceil \frac{t}{2}\right\rceil +u_{j'}\geq 2t+\left\lceil \frac{t}{2}\right\rceil +u_0+1\). Thus \(u_0 ^{''},u_{j'} ^{'}\in ⟦ 2t+\left\lceil \frac{t}{2}\right\rceil +u_0+1, 2t+3\left\lceil \frac{t}{2}\right\rceil ⟧\). Hence there exists at least \(2\left\lceil \frac{t}{2}\right\rceil -u_0+1\) elements in \(⟦ 2t+\left\lceil \frac{t}{2}\right\rceil +u_0+1, 2t+3\left\lceil \frac{t}{2}\right\rceil ⟧\), which implies \(2\left\lceil \frac{t}{2}\right\rceil -u_0+1 \leq 2\left\lceil \frac{t}{2}\right\rceil -u_0\), a contradiction.
In all cases we obtain a contradiction. Therefore, the claim follows.
Since the number of vertices of \(H\) whose colors are different from \(1\) and occur exactly twice in \(H\) is \(2\beta\), and the number of vertices of \(H\) with color \(1\) in \(H\) is \(\alpha\), hence the number of vertices of \(H\) whose colors are different from \(1\) and occur exactly once in \(H\) is \(k-\beta-1\). It follows that \(2t+3\left\lceil \frac{t}{2}\right\rceil +1 = \left\lvert V \right\rvert= 2\beta+\alpha +k-\beta-1=\beta+\alpha +k-1 \leq 2\left\lceil \frac{t}{2}\right\rceil -\alpha +2 +\alpha +k-1\leq k+ 2\left\lceil \frac{t}{2}\right\rceil +1\), which implies \(k\geq 2t+\left\lceil \frac{t}{2}\right\rceil\). Thus \(\chi_{S} (D(1,t))\geq 2t+\left\lceil \frac{t}{2}\right\rceil\).
Case 2. \(s>\left\lceil \frac{t}{2}\right\rceil\).
Let \(V=⟦ 0, 2t\left(s+2-\left\lceil \frac{t}{2}\right\rceil\right)+2\left\lceil \frac{t}{2}\right\rceil-1 ⟧\). Let \(H\) be a subgraph of \(D(1,t)\) with vertex set \(V\), let \(f\) be an S-packing k-coloring of subgraph \(H\) from \(V\) to \(\lbrace 1,2,\dots,k \rbrace\) with \(k\in \mathbb{N}^*\setminus \lbrace 1\rbrace\), let \(J'=⟦ 1, k ⟧\), \(J=J'\setminus \lbrace 1 \rbrace\), \(V_j=\lbrace i\in V :\; f(i)=j \rbrace\) where \(j\in J'\), and let \(\alpha =\left\lvert V_1\right\rvert\).
By Lemma 2.4, for all \(j\in J\), \(\left\lvert V_j\right\rvert \leq 2\). Let \(\beta =\bigl| \lbrace j\in J :\; \left\lvert V_j\right\rvert =2 \rbrace \bigr|\). Lemma 2.4 also implies that three vertices of \(V\) can be colored with color \(1\). Then \(1\leq \alpha \leq 3\).
Now we claim that \(\beta \leq t\left(s+2-\left\lceil \frac{t}{2}\right\rceil\right)+\left\lceil \frac{t}{2}\right\rceil -\alpha +1\). Suppose to the contrary that \(\beta > t\left(s+2-\left\lceil \frac{t}{2}\right\rceil\right)+\left\lceil \frac{t}{2}\right\rceil -\alpha +1\).
Since the number of vertices of \(H\) whose colors are different from \(1\) and occur exactly twice in \(H\) is \(2\beta\), and the number of vertices of \(H\) with color \(1\) in \(H\) is \(\alpha\), hence the number of vertices of \(H\) whose colors are different from \(1\) and occur exactly once in \(H\) is \(k-\beta-1=\left\lvert V\right\rvert-2\beta-\alpha\geq 0\). By the assumption, we have \(\left\lvert V\right\rvert-2\beta-\alpha <2t\left(s+2-\left\lceil \frac{t}{2}\right\rceil\right)+2\left\lceil \frac{t}{2}\right\rceil -2t\left(s+2-\left\lceil \frac{t}{2}\right\rceil\right)-2\left\lceil \frac{t}{2}\right\rceil +2\alpha -2-\alpha =\alpha-2\), then \(\left\lvert V\right\rvert -2\beta-\alpha \leq \alpha-3\). If \(\alpha \leq 2\), we obtain a contradiction since \(\left\lvert V\right\rvert -2\beta-\alpha\geq 0\). If \(\alpha =3\), then \(\left\lvert V\right\rvert -2\beta-\alpha =0\), which implies \(\left\lvert V \right\rvert =2\beta+3\), a contradiction since \(\left\lvert V\right\rvert\) is even. Consequently, the claim is true.
Since \(2t\left(s+2-\left\lceil \frac{t}{2}\right\rceil\right)+2\left\lceil \frac{t}{2}\right\rceil = \left\lvert V\right\rvert =k-\beta-1+2\beta+\alpha\), then \(k\geq t\left(s+2-\left\lceil \frac{t}{2}\right\rceil\right)+\left\lceil \frac{t}{2}\right\rceil\). Therefore \(\chi_{S} (D(1,t))\geq t\left(s+2-\left\lceil \frac{t}{2}\right\rceil\right)+\left\lceil \frac{t}{2}\right\rceil\). ◻
Theorem 3.1 and Theorem 3.2 yield the following result.
Corollary 3.3. Let \(t> 1\) be an integer and \(s\geq \max\left(\left\lceil \frac{t}{2}\right\rceil,t-3\right)\) be an integer, and let \(S=(s,s+1,s+1,\dots)\). Then \(\chi_{S} (D(1,t))= t\left(s+2-\left\lceil \frac{t}{2}\right\rceil\right)+\left\lceil \frac{t}{2}\right\rceil\).
These formulas determine \(\chi_S(D(1,t))\) over a broad, previously untreated range and complement earlier exact results for small–valued sequences (e.g., \((1,2,2,\dots)\)) [9]. In particular, they show that, once the sequence has stabilized at \(s+1\) with \(s\) not too small relative to \(t\), \(\chi_S(D(1,t))\) is exactly given by the explicit formula above.
In this section, we give a lower bound for \(\chi_{d} (D(1,t))\) where \(d\geq \left\lceil \frac{t}{2}\right\rceil\), and we determine the exact value of \(\chi_{d} (D(1,t))\) for \(d\geq \max\left(\left\lceil \frac{t}{2}\right\rceil,t-2\right)\).
Theorem 4.1. Let \(t> 1\) be an integer and \(d\geq \left\lceil \frac{t}{2}\right\rceil\) be an integer. Then \(\chi_{d} (D(1,t))\geq t\left(d+1-\left\lceil \frac{t}{2}\right\rceil\right)+\left\lceil \frac{t}{2}\right\rceil\).
Proof. Let \(V=⟦ 0,
t\left(d+1-\left\lceil \frac{t}{2}\right\rceil\right)+\left\lceil
\frac{t}{2}\right\rceil-1 ⟧\), let \(H\) be a subgraph of \(D(1,t)\) with vertex set \(V\), let \(f\) be an S-packing k-coloring of subgraph
\(H\) from \(V\) to \(⟦ 1,k ⟧\) with
\(k\in \mathbb{N}^*\), and let \(J=⟦ 1,k ⟧\)
and \(V_j=\lbrace i\in V :\; f(i)=j
\rbrace\) with \(j\in J\).
Let \(j\in J\). From Lemma 2.4, \(\left\lvert V_j\right\rvert \leq 1\). Then
\(\left\lvert
V\right\rvert =t\left(d+1-\left\lceil
\frac{t}{2}\right\rceil\right)+\left\lceil \frac{t}{2}\right\rceil
= \displaystyle{ \sum_{j\in J } \left\lvert V_j\right\rvert } \leq
k\), thus \(k\geq
t\left(d+1-\left\lceil \frac{t}{2}\right\rceil\right)+\left\lceil
\frac{t}{2}\right\rceil\).
Therefore \(\chi_{d} (D(1,t)\geq t\left(d+1-\left\lceil \frac{t}{2}\right\rceil\right)+\left\lceil \frac{t}{2}\right\rceil\). ◻
Combining Theorem 3.1 and Theorem 4.1 yields the following corollary.
Corollary 4.2. Let \(t> 1\) be an integer and \(d\geq \max\left(\left\lceil \frac{t}{2}\right\rceil,t-2\right)\) be an integer. Then \(\chi_{d} (D(1,t))= t\left(d+1-\left\lceil \frac{t}{2}\right\rceil\right)+\left\lceil \frac{t}{2}\right\rceil\).
In this section, we investigate \((1,s,s,\dots)\)–packing colorings of the distance graphs \(D(1,t)\) for \(s \ge \left\lceil \frac{t}{2} \right\rceil\). Prior work has focused mainly on small–valued or specially structured sequences. Přemysl Holub and Jakub Hofman showed that \(\chi_{(1,2,2,\ldots)}(D(1,t))=5\) for \(t>1\), and that \(\chi_{(1,3,3,\ldots)}(D(1,t))=5\) when \(t\) is odd [9]. As far as we are aware, no systematic study of the broader family \((1,s,s,\ldots)\) with \(s \ge \left\lceil \frac{t}{2} \right\rceil\) has been undertaken.
Here we derive general lower bounds for \(\chi_{S}(D(1,t))\) with \(S=(1,s,s,\ldots)\), and, under suitable conditions on \(s\) and \(t\), provide constructive upper bounds that match them, thereby yielding exact values in several cases.
We first bound how many vertices can receive color \(i\) with \(s_i=1\) inside an interval; this will be used in both lower and upper bounds.
Lemma 5.1. Let \(t>1\) be an integer and let \(S=(s_i)_{i\geq 1}\) be a non-decreasing sequence in \(\mathbb{N}^*\). Let \(x,y \in \mathbb{Z}\) with \(x<y\), and let \(H\) be a subgraph of the distance graph \(D(1,t)\) with vertex set \(V = ⟦ x,y ⟧\). Let \(f\) be an S-packing k-coloring of \(H\), where \(k \in \mathbb{N}^*\), and let \(y-x = (t+1)q + r\) with \(q,r \in \mathbb{N}\) and \(0 \leq r < t+1\). If there exists an integer \(i\) with \(1 \leq i \leq k\) such that \(s_i=1\), then:
(a) If \(t\) is even and \(r\neq t\), then \[\bigl|\{\,v\in V : f(v)=i\,\}\bigr| \;\le\; q\cdot \tfrac{t}{2} + \left\lfloor \tfrac{r}{2} \right\rfloor + 1.\]
(b) If \(t\) is even and \(r=t\), then \[\bigl|\{\,v\in V : f(v)=i\,\}\bigr| \;\le\; (q+1)\tfrac{t}{2}.\]
(c) If \(t\) is odd, then \[\bigl|\{\,v\in V : f(v)=i\,\}\bigr| \;\le\; 1 + \left\lfloor \tfrac{y-x}{2} \right\rfloor .\]
Proof. Let \(V^{\prime}=\lbrace v\in V :\; f(v)=i \rbrace\) be the set of vertices of \(V\) colored \(i\). Let \(u_0,v_0\in V\) with \(v_0>u_0\), and set \(U=\lbrace v\in ⟦ u_0,v_0⟧ :\; f(v)=i \rbrace\) and \(m=\left\lvert U\right\rvert\).
For any distinct \(u,v \in U\) with \(v>u\), we have \(f(u)=f(v)=i\). Since \(s_i=1\), this implies \(v-u \ge 2\). Let \(x_1 < x_2 < \dots < x_{m}\) be the elements of \(U\). It follows that \(x_{m} \ge x_1 + 2(m-1)\). Since \(x_{m}\le v_0\) and \(x_1 \ge u_0\), we conclude that \(m \leq \left\lfloor \frac{v_0-u_0}{2} \right\rfloor +1\). Therefore, \(m \leq \left\lfloor \frac{y-x}{2} \right\rfloor +1\). This completes the proof for the case when \(t\) is odd.
We claim that if \(v_0-u_0=t\), then \(m \leq \left\lfloor \frac{v_0-u_0}{2} \right\rfloor\).
Suppose that \(v_0-u_0=t\). Since
\(x_{1}\) and \(x_{m}\) are both colored \(i\), then \(x_{m}-x_{1}\neq t\), which implies \(v_0\neq x_{m}\) or \(u_0\neq x_{1}\).
Suppose to the contrary that \(m \geq
\left\lfloor \frac{v_0-u_0}{2} \right\rfloor+1
= \frac{t}{2}+1\).
Since \(x_{m} \ge x_1 + 2(m-1)=x_1 +t\) and (\(x_{m}< v_0\) or \(x_1 > u_0\)), then \(v_0> u_0 +t\), a contradiction, as claimed.
Case 1. \(t\) is even and \(r\neq t\).
If \(q=0\), then \(y-x=r\). Since \(x,y\in V\), \(\left\lvert V^{\prime}\right\rvert \leq \left\lfloor\frac{y-x}{2}\right\rfloor+1=\left\lfloor \frac{r}{2}\right\rfloor +1\).
If \(q\neq 0\), then let \(V_q= ⟦ x+q(t+1),x+q(t+1)+r⟧\) and \(V_n= ⟦ x+n(t+1),x+n(t+\) \(1)+t⟧\) where \(n\in ⟦ 0,q-1 ⟧\). Let \(V_n^{\prime}=\lbrace v\in V_n :\;f(v)=i \rbrace\) where \(n\in ⟦ 0,q ⟧\). Observe that \(V=\displaystyle{\bigcup_{n=0}^{q} V_n}\) and \(V^{\prime}=\displaystyle{\bigcup_{n=0}^{q} V_n^{\prime}}\) where the unions are disjoint. Then \(\left\lvert V^{\prime}\right\rvert =\displaystyle{ \sum_{n=0}^{q} \left\lvert V_n^{\prime} \right\rvert }\). Since for every \(n\in ⟦ 0,q-1 ⟧\), \(\left\lvert V_n^{\prime}\right\rvert \leq \frac{t}{2}\) and \(\left\lvert V_q^{\prime} \right\rvert \leq \left\lfloor\frac{r}{2}\right\rfloor +1\), hence \(\left\lvert V^{\prime} \right\rvert \leq q\frac{t}{2} +\left\lfloor\frac{r}{2}\right\rfloor +1\).
Case 2. \(t\) is even and \(r= t\).
Let \(V_n= ⟦ x+n(t+1),x+n(t+1)+t⟧\) where \(n\in ⟦ 0,q ⟧\). Let \(V_n^{\prime}~=~\lbrace v\in~ V_n :~\; ~f(v)=~i~ \rbrace\) where \(n\in ⟦ 0,q ⟧\). As before, \(V=\displaystyle{\bigcup_{n=0}^{q} V_n}\) and \(V^{\prime}=\displaystyle{\bigcup_{n=0}^{q} V_n^{\prime}}\) where the unions are disjoint. Since for every \(n\in ⟦ 0,q ⟧\), \(\left\lvert V_n^{\prime} \right\rvert \leq \frac{t}{2}\), hence \(\left\lvert V^{\prime} \right\rvert \leq (q+1)\frac{t}{2}\). ◻
We now derive a general lower bound for \(\chi_S(D(1,t))\) when \(t\) is odd and \(S=(1,s,s,\dots)\) with \(s\geq \frac{t+1}{2}\). The following theorem provides an explicit expression that depends on the parity of \(s\).
Theorem 5.2. Let \(t> 1\) be an odd integer and \(s\geq \dfrac{t+1}{2}\) be an integer, and let \(S=(1,s,s,\dots)\). Then:
(a) If \(s\) is odd, then \[\chi_S\bigl(D(1,t)\bigr)\;\ge\; \frac{\,t\!\left(s+1-\left\lceil \tfrac{t}{2}\right\rceil\right)+\left\lceil \tfrac{t}{2}\right\rceil\,}{2}\;+\;1.\]
(b) If \(s\) is even, then \[\chi_S\bigl(D(1,t)\bigr)\;\ge\; \frac{\,t\!\left(s+1-\left\lceil\tfrac{t}{2}\right\rceil\right)+\left\lceil \tfrac{t}{2}\right\rceil+1\,}{2}.\]
Proof. We set \(N=t(s+1-\left\lceil \frac{t}{2}\right\rceil)+\left\lceil \frac{t}{2}\right\rceil\) and \(V=⟦ 0, N-1 ⟧\). Let \(H\) be a subgraph of \(D(1,t)\) with vertex set \(V\). Let \(f\) be an S-packing k-coloring of subgraph \(H\) with \(k\in \mathbb{N}^*\). Clearly \(k\geq 2\). Set \(J'=⟦ 1,k ⟧\), \(J=J'\setminus \lbrace 1 \rbrace\) and \(V_j=\lbrace i\in V :\; f(i)=j \rbrace\) where \(j\in J'\).
By Lemma 5.1 we obtain \(|V_1|\leq \left\lfloor \dfrac{N-1}{2}\right\rfloor +1\), and by Lemma 2.4 it follows that \(|V_j|\leq 1\).
Since \(N=\left\lvert V \right\rvert =\displaystyle{ \sum_{j\in J' } \left\lvert V_j \right\rvert }= \displaystyle{\left\lvert V_1 \right\rvert +\sum_{j=2 }^{k} \left\lvert V_j \right\rvert }\), hence \(N \leq \left\lfloor \dfrac{N-1}{2}\right\rfloor +1+k-1\), which implies \(k \geq N-\left\lfloor \dfrac{N-1}{2}\right\rfloor\). It follows that \(\chi _S (H)\geq~ N-\left\lfloor \dfrac{N-1}{2}\right\rfloor\). Thus, if \(s\) is odd, then \(N\) is even, then \(\chi _S (H)\geq \dfrac{N}{2}+1\), otherwise, if \(s\) is even, then \(N\) is odd \(\chi _S (H)\geq \dfrac{N +1}{2}\). Therefore, by Observation 2.2, we deduce the result. ◻
Theorem 5.3. Let \(t> 1\) be an odd integer and \(s\geq t-2\) be an integer, and let \(S=(1,s,s,\dots)\). If \(s\) is odd, then \(\chi _S (D(1,t)) \leq \dfrac{t(s+1-\left\lceil \frac{t}{2}\right\rceil)+\left\lceil \frac{t}{2}\right\rceil}{2}+1\).
Proof. Suppose that \(s\)
is odd. Set \(k=t(s+1-\left\lceil
\frac{t}{2}\right\rceil)+\left\lceil \frac{t}{2}\right\rceil+1\)
and
\(V=⟦ 0,
k-2⟧\). Let \(g\)
be a mapping from \(V\) to \(⟦ 1,k ⟧\),
defined by \[g(i)=
\begin{cases}
1, & \text{if} \; i\; is \; even;\\
j+2, & \text{if}\; i=2j+1 \; with \; j\in \mathbb{N},
\end{cases}\] for all \(i\in
V\) .
And let \(f\) be a mapping from \(\mathbb{Z}\) to \(⟦ 1,k ⟧\), defined by \(f(i)= g(i_0)\) for all \(i \equiv i_0 \pmod{k-1}\) with \(0\leq i_0<k-1\).
It is clear that \(g\) and \(f\) are well defined. Now we show that \(f\) is S-packing k-coloring.
Let \(i,i' \in \mathbb{Z}\) with \(i\neq i'\), such that \(f(i)=f(i')=j_0\). There exists \(l,l'\in \mathbb{Z}\) and \(i_0,i_0'\in ⟦ 0, k-2⟧\) such that \(i=l(k-1)+i_0\) and \(i'=l'(k-1)+i_0'\), then \(g(i_0)=f(i)=j_0=f(i')=g(i_0')\).
For color \(1\). Suppose that \(j_0=1\). Since \(g(i_0)=g(i_0')=1\), both \(i_0\) and \(i_0'\) are even. Because \(s\) is odd, it follows that \(k-1\) is even, which implies that both \(i\) and \(i'\) are even. Hence \(\left\lvert i'-i\right\rvert\) is even, and therefore \(\left\lvert i'-i\right\rvert \notin \{1,t\}\). Consequently, \(i\) and \(i'\) are not adjacent, and thus \(d_{D(1,t)}(i,i')>1\).
For color \(j_0\neq 1\). Suppose that \(j_0\neq 1\). Since \(g(i_0)=g(i_0')=j_0>~1\), both \(i_0\) and \(i_0'\) are odd. Hence, by definition of mapping \(g\), we have \(i_0=2(j_0-2)+1=i_0'\). It follows that \(| i'-i | = | (l'-l ) (k-1)-0 |\), then \(d_{D(1,t)}(i,i')=d_{D(1,t)}(0,| l'-l | (k-1))\). We have \(| l'-l | \in \mathbb{N}^*\) and \(s+1\geq t-1\), hence it follows from Lemma 2.5 that \(d_{D(1,t)}(0,| l'-l | (k-1))=d_{D(1,t)}(0,| l'-l | t(s+1-\left\lceil \frac{t}{2}\right\rceil)+| l'-l | \left\lceil \frac{t}{2}\right\rceil ) \geq s+1\), thus \(d_{D(1,t)}(i,i')\geq s+1\).
Therefore \(f\) is S-packing k-coloring. ◻
Theorem 5.2 and Theorem 5.3 imply the following result.
Corollary 5.4. Let \(t> 1\) be an odd integer and let \(s\geq \max( t-2, \dfrac{t+1}{2} )\) be an integer. If \(s\) is odd, then \(\chi _S (D(1,t)) = \dfrac{t(s+1-\left\lceil \frac{t}{2}\right\rceil)+\left\lceil \frac{t}{2}\right\rceil}{2}+1 .\)
We now establish an upper bound for \(\chi _S (D(1,t))\) when \(t\) is even and \(s\ge\max(1,t-2)\).
Theorem 5.5. Let \(t>1\) be an even integer and let \(s\ge\max(1,t-2)\) be an integer, and let \(S=(1,s,s,\dots)\). If \(r\) is even and \(r \neq t\), then \(\chi _S (D(1,t)) \leq ( \frac{t}{2}+1)q+r+1\), where \(t(s+1-\frac{t}{2})+\frac{t}{2}=(t+1)q+r\) with \(q,r\in \mathbb{N}\) and \(0 \leq r<t+1\).
Proof. Suppose that \(r\) is even and \(r \neq t\). Then \(0 \leq r <t-1\). And we have \(s\geq \max(1,t-2)\), then \(q \geq 1\).
Let \(k=(1+\frac{t}{2})q+r+1\), \(V=⟦ 0,(t+1)q+r-1 ⟧\), \[A_1=\left\lbrace i\in V :\; i=(t+1)q^{'}+2r^{'}+r+2 \; with \; 0\leq q^{'}< q \; and \; 0 \leq r^{'}<\frac{t}{2}\right\rbrace ,\] and \(A_2=V\setminus A_1\). Clearly \(A_1 \neq \emptyset\) and \(A_2 \neq \emptyset\). Since \(A_2\) is a nonempty finite set, implies that there exists a strictly increasing sequence \((y_p)_{1\leq p\leq p_0}\) in \(V\) (with \(p_0=\left\lvert A_2 \right\rvert =\left\lvert V \right\rvert -\left\lvert A_1\right\rvert =\left(\frac{t}{2}+1\right)q+r\)) such that \(A_2=\lbrace y_1,y_2,\dots,y_{p_0}\rbrace\).
Let \(g\) be a mapping from \(V\) to \(⟦ 1,k ⟧\), defined by \[g(i)=\begin{cases} 1 ,\; if \; i\in A_1 ; \\ j+1 ,\; if\; i=y_j\in A_2 \; with \; j\in ⟦ 1,p_0⟧ , \end{cases}\] for all \(i\in V\) .
And let \(f\) be a mapping from \(\mathbb{Z}\) to \(⟦ 1,k ⟧\), defined by \(f(i)= g(i_0)\) for all \(i \equiv i_0 \pmod{(t+1)q+r}\) with \(0\leq i_0<(t+1)q+r\).
It is clear that \(g\) and \(f\) are well defined. Now we show that \(f\) is S-packing k-coloring.
Let \(i,i^{'} \in \mathbb{Z}\) with \(i< i^{'}\), such that \(f(i)=f(i^{'})=j_0\). There exists \(l,l^{'}\in \mathbb{Z}\) and \(i_1,i_2\in V\) such that \(i=l((t+1)q+r)+i_1\) and \(i^{'}=l^{'}((t+1)q+r)+i_2\), then \(g(i_1)=f(i)=j_0=f(i^{'})=g(i_2)\). Since \(i< i^{'}\), then \(l^{'}\geq l\), hence \(l^{'}-l\geq 0\).
Case 1. \(j_0= 1\) and \(l^{'} – l \geq 2\).
We have \(i^{'}-i = (l^{'} – l)((t+1)q+r)+i_2-i_1\geq (t+1)q+r+1 > t\) (since \(i_2-i_1\geq -(t+1)q-r+1\) and \(q \geq 1\)), which implies \(i^{'}\) and \(i\) are not adjacent. Therefore \(d_{D(1,t)}(i,i^{'})>1\).
Case 2. \(j_0= 1\) and \(l^{'} – l = 1\) and \(i_1\leq i_2\).
Since \(i^{'}-i = (t+1)q+r+i_2-i_1\geq (t+1)q+r> t\), thus \(i^{'}\) and \(i\) are not adjacent. Therefore \(d_{D(1,t)}(i,i^{'})>1\).
Case 3. \(j_0= 1\) and \(l^{'} – l = 1\) and \(i_1> i_2\).
Since \(i_1,i_2\in A_1\), then there exists \(q_1,q_2 \in ⟦ 0, q-1 ⟧\) and \(r_1,r_2 \in ⟦ 0 ,\frac{t}{2}-1 ⟧\) such that \(i_1=(t+1)q_1+2r_1+r+2\) and \(i_2=(t+1)q_2+2r_2+r+2\). Hence \(i^{'}-i=(t+1)q+r+i_2-i_1\geq r+3>1\).
We prove by contradiction that \(i^{'}-i\neq t\). Suppose that \(i^{'}-i= t\). Then \(i_1=(t+1)q+r+i_2-t\). Since \(i_2=(t+1)q_2+2r_2+r+2\), hence \(i_1= (t+1)(q+q_2)+2(\frac{r}{2}+r_2-\frac{t}{2})+r+2\).
If \(\frac{r}{2}+r_2-\frac{t}{2} \geq 0\), then \(i_1 \geq (t+1)q+r+2> (t+1)q+r-1\), hence \(i_1 \notin V\), a contradiction since \(i_1\in V\).
If \(\frac{r}{2}+r_2-\frac{t}{2} < 0\), then \(0 \leq \frac{r}{2}+r_2 < \frac{t}{2}\), then \(i_1=(t+1)(q+q_2-1)+2\left(\frac{r}{2}+r_2\right)+r+2+1\), hence \(i_1 \notin A_1\), a contradiction since \(i_1\in A_1\).
Thus \(i^{'}\) and \(i\) are not adjacent. Therefore \(d_{D(1,t)}(i,i^{'})>1\).
Case 4. \(j_0= 1\) and \(l^{'} – l = 0\).
Since \(g(i_1)=g(i_2)=1\), \(i_1,i_2\in A_1\). Then there exists \(q_1,q_2 \in ⟦ 0, q-1 ⟧\) and \(r_1,r_2 \in ⟦ 0 ,\frac{t}{2}-1 ⟧\) such that \(i_1=(t+1)q_1+2r_1+r+2\) and \(i_2=(t+1)q_2+2r_2+r+2\). If \(q_2-q_1 =0\), then \(i^{'}-i = i_2-i_1=2r_2-2r_1<t\), which implies \(0<i^{'}-i <t\) and \(i^{'}-i\) is even, hence \(i^{'}-i \notin \lbrace-t,-1,1,t \rbrace\). If \(q_2-q_1 =1\), then \(i^{'}-i = t+1+2r_2-2r_1<t\), which implies \(i^{'}-i >1\) and \(i^{'}-i\) is odd, hence \(i^{'}-i \notin \lbrace-t,-1,1,t \rbrace\). If \(q_2-q_1 >1\), then \(i^{'}-i >t\), which implies \(i^{'}-i \notin \lbrace-t,-1,1,t \rbrace\).
Thus \(i^{'}\) and \(i\) are not adjacent. Therefore \(d_{D(1,t)}(i,i^{'})>1\).
Case 5. \(j_0> 1\).
Since \(j_0\neq 1\), implies that \(i_1\) and \(i_2\) are in \(A_2\). And we have \(g(i_1)=g(i_2)=j_0\), then \(i_1=y_{j_0-1}=i_2\). Hence \(i^{'}-i = ( l^{'} – l ) ((t+1)q+r)\), then \(d_{D(1,t)}(i,i^{'})=d_{D(1,t)}(0,( l^{'}-l ) ((t+1)q+r))\) . We have \(l^{'}-l \in \mathbb{N}^*\) and \(s+1\geq t-1\), hence it follows from Lemma 2.5 that \(d_{D(1,t)}(0,( l^{'}-l ) ((t+1)q+r))=d_{D(1,t)}(0,( l^{'}-l ) t(s+1-\left\lceil \frac{t}{2}\right\rceil)+( l^{'}-l ) \left\lceil \frac{t}{2}\right\rceil ) \geq s+1\), then \(d_{D(1,t)}(i,i^{'})\geq s+1\).
Thus \(f\) is S-packing k-coloring. Therefore \(\chi _S (D(1,t)) \leq ( \frac{t}{2}+1)q+r+1\). ◻
Theorem 5.6. Let \(t> 1\) be an even integer and \(s\geq \frac{t}{2}\) be an integer, and let \(S=(1,s,s,\dots)\). Then, \[\chi_S\bigl(D(1,t)\bigr)\;\ge\; \begin{cases} \left(\frac{t}{2} + 1\right)q+ \left\lceil \frac{r+1}{2} \right\rceil, & \text{if } r\neq 0;\\ \left(\frac{t}{2} + 1\right)q+1, & \text{otherwise }, \end{cases}\] where \(t\left(s+1-\frac{t}{2}\right)+\frac{t}{2}=(t+1)q+r\) with \(q,r\in \mathbb{N}\) and \(0 \leq r<t+1\).
Proof. Let \(V=⟦ 0,(t+1)q+r-1 ⟧\), and \((t+1)q+r-1-0 = (t+1)q^{\prime}+r^{\prime}\). Let \(H\) be a subgraph of \(D(1,t)\) with vertex set \(V\), and let \(f\) be an S-packing \(k-coloring\) of subgraph \(H\) with \(k\in \mathbb{N}^*\). Clearly \(k\geq 2\). Let \(J'=⟦ 1,k ⟧\) and \(J=J'\setminus \lbrace 1 \rbrace\) and \(V_j=\lbrace v\in V :\; f(v)=j \rbrace\) and \(a_j=\left\lvert V_j \right\rvert\) with \(j\in J'\).
By Lemma 2.4, \(a_j\leq 1\) for every \(j\in J\).
Case 1. \(r\neq 0\).
Since \((t+1)q+r-1 = (t+1)q^{\prime}+r^{\prime}\) and \(r\neq 0\), \(q^{\prime}=q\) and \(r^{\prime}=r-1<t\). Then by Lemma 5.1, \(a_1\leq q^{\prime} \frac{t}{2}+\left\lfloor \frac{r^{\prime}}{2} \right\rfloor+1=q \frac{t}{2}+\left\lfloor \frac{r-1}{2} \right\rfloor+1\). Since \[(t+1)q+r=\left\lvert V \right\rvert =\displaystyle{ \sum_{j\in J' } \left\lvert V_j \right\rvert }= \displaystyle{a_1+\sum_{j=2 }^{k} a_j}\leq q \frac{t}{2}+\left\lfloor \frac{r-1}{2} \right\rfloor+1+k-1,\] then \(k \geq \left(\frac{t}{2} + 1\right)q+ \left\lceil \frac{r+1}{2} \right\rceil\). Hence \(\chi _S (H)\geq \left(\frac{t}{2} + 1\right)q+ \left\lceil \frac{r+1}{2} \right\rceil\). Therefore, by Observation 2.2, \(\chi _S (D(1,t)) \geq \left(\frac{t}{2} + 1\right)q+ \left\lceil \frac{r+1}{2} \right\rceil\).
Case 2. \(r=0\). Then \(q' = q-1\) and \(r' = t\). Hence, from Lemma 5.1 we obtain \(a_1\leq q \frac{t}{2}\). Again \[(t+1)q+r=\left\lvert V \right\rvert =\displaystyle{a_1+\sum_{j=2 }^{k} a_j}\leq q \frac{t}{2}+k-1,\] so \(k \geq \left(\frac{t}{2} + 1\right)q+1\). It follows that \(\chi _S (H)\geq \left(\frac{t}{2} + 1\right)q+1\), and consequently \(\chi _S (D(1,t)) \geq \left(\frac{t}{2} + 1\right)q+1\). ◻
The next corollary follows immediately from Theorem 5.5 and Theorem 5.6.
Corollary 5.7. Let \(t> 1\) be an even integer and \(s\geq \max(t-2,\frac{t}{2})\) be an integer, and let \(S=(1,s,s,\dots)\) and \(t(s+1-\frac{t}{2})+\frac{t}{2}=(t+1)q+r\) with \(q,r\in \mathbb{N}\) and \(0 \leq r<t+1\). Then:
(a) If \(r\) is even and \(r \notin \{0,t\}\), then \[\left(\frac{t}{2} + 1\right)q + \tfrac{r}{2} + 1 \;\leq\; \chi_S\bigl(D(1,t)\bigr) \;\leq\; \left(\frac{t}{2} + 1\right)q + r + 1.\]
(b) If \(r=0\), then \[\chi_S\bigl(D(1,t)\bigr) = \left(\frac{t}{2} + 1\right)q + 1.\]
In other words, if \(s = (t+1)a + t – 1\) with \(a\in \mathbb{N}\), then \[\chi_S\bigl(D(1,t)\bigr) = \left(\frac{t}{2} + 1\right)q + 1.\]
We conclude this paper with several illustrative computations of \(\chi_S\!\bigl(D(1,t)\bigr)\) obtained by applying our corollaries. These examples illustrate the exactness of our results and their behavior for different values of \(S\) and \(t\).
Example 5.8. (a) For \(S=(1,3,3,\ldots)\) and \(t=4\), Corollary 5.7 gives \(\chi_S\!\bigl(D(1,4)\bigr)=7\).
(b) For \(S=(1,4,4,\ldots)\) and \(t=2\), Corollary 5.7 gives \(\chi_S\!\bigl(D(1,2)\bigr)=7\).
(c) For \(S=(2,3,3,\ldots)\) (i.e., \((s,s+1,s+1,\ldots)\) with \(s=2\)), Corollary 3.3 yields \(\chi_S\!\bigl(D(1,2)\bigr)=7\) and \(\chi_S\!\bigl(D(1,3)\bigr)=8\).
(c) For \(S=(1,3,3,\ldots)\) and \(t\in\{5,3\}\), Corollary 5.4 gives \(\chi_S\!\bigl(D(1,5)\bigr)=5\) and \(\chi_S\!\bigl(D(1,3)\bigr)=5\).
(d) For \(S=(1,7,7,\ldots)\) and \(t\in\{9,7,5,3\}\), Corollary 5.4 gives \(\chi_S\!\bigl(D(1,9)\bigr)=17\), \(\chi_S\!\bigl(D(1,7)\bigr)=17\), \(\chi_S\!\bigl(D(1,5)\bigr)=15\), and \(\chi_S\!\bigl(D(1,3)\bigr)=11\).