\(\left(s,s+1,s+1,\dots\right)\)-packing colorings and \(\left(1,s,s,\dots\right)\)-packing colorings and d-distance colorings of distance graphs \(D(1,t)\)
<p>An S-packing k-coloring of a graph <span class="math inline">\(G\)</span> (with <span class="math inline">\(S=(s_1,s_2,\dots)\)</span> is a non-decreasing sequence of positive integers) is a mapping <span class="math inline">\(f\)</span> from <span class="math inline">\(V(G)\)</span> to <span class="math inline">\(\lbrace 1,\dots , k \rbrace\)</span> (the set of colors) such that for every two distincts vertices <span class="math inline">\(x\)</span> and <span class="math inline">\(y\)</span> in <span class="math inline">\(V(G)\)</span> with <span class="math inline">\(f(x)=f(y)=i\)</span> the distance between <span class="math inline">\(x\)</span> and <span class="math inline">\(y\)</span> in <span class="math inline">\(G\)</span> is bigger than <span class="math inline">\(s_i\)</span>. The S-packing chromatic number <span class="math inline">\(\chi_S (G)\)</span> of <span class="math inline">\(G\)</span> is the smallest integer <span class="math inline">\(k\)</span> such that <span class="math inline">\(G\)</span> has an S-packing k-coloring. Given a set <span class="math inline">\(D\subset \mathbb{N}^*\)</span>, a distance graph <span class="math inline">\(G(\mathbb{Z}, D)\)</span> with distance set <span class="math inline">\(D\)</span> is a graph with vertex set <span class="math inline">\(\mathbb{Z}\)</span> and two distincts vertices <span class="math inline">\(u\)</span> and <span class="math inline">\(v\)</span> are adjacents if <span class="math inline">\(| u-v | \in D\)</span>. In this paper, for <span class="math inline">\(S=(s,s+1,s+1,\dots)\)</span> with <span class="math inline">\(s \geq \left\lceil \frac{t}{2} \right\rceil\)</span> we give a lower bound of <span class="math inline">\(\chi_S (G(\mathbb{Z}, \lbrace 1, t\rbrace))\)</span>, and a lower bound of <span class="math inline">\(\chi_d (G(\mathbb{Z}, \lbrace 1, t\rbrace))\)</span> with <span class="math inline">\(d \geq \left\lceil \frac{t}{2} \right\rceil\)</span>, for <span class="math inline">\(S=(s_1,s_2,\dots, s_i,a,a,\dots)\)</span> with <span class="math inline">\(a \geq \max( 1 , t-2 )\)</span> we give an upper bound of <span class="math inline">\(\chi_S (G(\mathbb{Z}, \lbrace 1, t\rbrace))\)</span>, and we determine the exact values of <span class="math inline">\(\chi_S (G(\mathbb{Z}, \lbrace 1, t\rbrace))\)</span> and also of <span class="math inline">\(\chi_d (G(\mathbb{Z}, \lbrace 1, t\rbrace))\)</span> for <span class="math inline">\(s\geq \max (\left\lceil \frac{t}{2} \right\rceil, t-3)\)</span> and <span class="math inline">\(d \geq \max (\left\lceil \frac{t}{2} \right\rceil , t-2)\)</span>. And we give a lower and an upper bound of <span class="math inline">\(\chi_S (G(\mathbb{Z}, \lbrace 1, t\rbrace))\)</span> for <span class="math inline">\(S=(1,s,s,\dots)\)</span> with conditions on <span class="math inline">\(s\)</span> and <span class="math inline">\(t\)</span>, which in the cases <span class="math inline">\(s\geq \max (t-2,\left\lceil \frac{t}{2}\right\rceil)\)</span> we determine the exact values of <span class="math inline">\(\chi_S (G(\mathb b{Z}, \lbrace 1, t\rbrace))\)</span>.</p>
Authors
- Latifa Faouzi
- Youssef El Kouabli
Publication Details
- Journal
- Journal of Combinatorial Mathematics and Combinatorial Computing
- Published
- 2025-09-28
- DOI
- https://doi.org/10.61091/jcmcc127-17
- Primary Topic
- Advanced Graph Theory Research
- Type
- article
- Field-Weighted Citation Impact
- 0.00