S-packing chromatic critical paths and cycles
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917380901306368 |
|---|---|
| author | Ekinci, Gülnaz Boruzanlı Bujtás, Csilla Gözüpek, Didem Gür, Aslıhan |
| author_facet | Ekinci, Gülnaz Boruzanlı Bujtás, Csilla Gözüpek, Didem Gür, Aslıhan |
| contents | Let $S=(s_1,s_2,\ldots)$ be a non-decreasing sequence of positive integers. For a graph $G$ with vertex set $V(G)$, a labeling $ϕ\colon V(G)\to \{1,\ldots,k\}$ is an $S$-packing $k$-coloring if, whenever two distinct vertices $u,v\in V(G)$ are assigned the same color $i$, their distance in $G$ is greater than $s_i$. The minimum $k$ for which $G$ admits such a coloring is the $S$-packing chromatic number of $G$. A graph $G$ is $χ_S$-vertex-critical if $χ_S(G-v) < χ_S(G)$ for every $v \in V(G)$, and it is $χ_S$-critical if $χ_S(H) < χ_S(G)$ holds for every proper subgraph $H$ of $G$. In this paper, the exact value of $χ_S(P_n)$ is determined for every path of order $n$ and for every packing sequence $S$ where $s_i < 2^i$ holds for each entry $s_i$. As a consequence, $χ_S$-critical and $χ_S$-vertex-critical paths are identified for each such sequence $S$. In addition, we extend earlier results on $χ_S$-critical cycles and provide a complete characterization of $χ_S$-critical and $χ_S$-vertex-critical cycles for packing sequences $S= (1, s_2, \dots )$ with $s_2 \in \{2,3\}$ and $s_3,s_4 \in \{4,5,6,7\}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_02267 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | S-packing chromatic critical paths and cycles Ekinci, Gülnaz Boruzanlı Bujtás, Csilla Gözüpek, Didem Gür, Aslıhan Combinatorics 05C15, 05C12 Let $S=(s_1,s_2,\ldots)$ be a non-decreasing sequence of positive integers. For a graph $G$ with vertex set $V(G)$, a labeling $ϕ\colon V(G)\to \{1,\ldots,k\}$ is an $S$-packing $k$-coloring if, whenever two distinct vertices $u,v\in V(G)$ are assigned the same color $i$, their distance in $G$ is greater than $s_i$. The minimum $k$ for which $G$ admits such a coloring is the $S$-packing chromatic number of $G$. A graph $G$ is $χ_S$-vertex-critical if $χ_S(G-v) < χ_S(G)$ for every $v \in V(G)$, and it is $χ_S$-critical if $χ_S(H) < χ_S(G)$ holds for every proper subgraph $H$ of $G$. In this paper, the exact value of $χ_S(P_n)$ is determined for every path of order $n$ and for every packing sequence $S$ where $s_i < 2^i$ holds for each entry $s_i$. As a consequence, $χ_S$-critical and $χ_S$-vertex-critical paths are identified for each such sequence $S$. In addition, we extend earlier results on $χ_S$-critical cycles and provide a complete characterization of $χ_S$-critical and $χ_S$-vertex-critical cycles for packing sequences $S= (1, s_2, \dots )$ with $s_2 \in \{2,3\}$ and $s_3,s_4 \in \{4,5,6,7\}$. |
| title | S-packing chromatic critical paths and cycles |
| topic | Combinatorics 05C15, 05C12 |
| url | https://arxiv.org/abs/2604.02267 |