\(\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

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
article

\(\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)\)

Latifa Faouzi, Youssef El Kouabli
Journal of Combinatorial Mathematics and Combinatorial Computing
Advanced Graph Theory Research
article

\(\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)\)

Latifa Faouzi, Youssef El Kouabli
article en

Abstract

<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>

Journal of Combinatorial Mathematics and Combinatorial ComputingVol. 127
Openalex Percentile: Top 72%
Advanced Graph Theory Research
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.