S-packing chromatic critical paths and cycles
Gülnaz Boruzanlı Ekinci, Csilla Bujtás, Didem Gözüpek, Aslıhan Gür · 2026
Read S-packing chromatic critical paths and cycles by Gülnaz Boruzanlı Ekinci, Csilla Bujtás, Didem Gözüpek, Aslıhan Gür (2026) 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-2604-02267.txt.
Introduction
Ekinci and colleagues determine exact S-packing chromatic numbers for paths and cycles. For a non decreasing sequence of positive integers, an S-packing coloring requires same color vertices to sit farther apart than the color index allows. They pin the exact number for every path under sequences meeting a per entry condition, naming critical and vertex critical paths. They extend earlier cycle results to a full account of critical and vertex critical cycles for sequences meeting two conditions.
Catalog record
| CREATOR | Gülnaz Boruzanlı Ekinci, Csilla Bujtás, Didem Gözüpek, Aslıhan Gür |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 44780 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.02267
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
S-packing chromatic critical paths and cycles Gülnaz Boruzanlı Ekinci, Csilla Bujtás, Didem Gözüpek, Aslıhan Gür Abstract Let S = ( s 1 , s 2 , … ) S=(s_{1},s_{2},\ldots) be a non-decreasing sequence of positive integers. For a graph G G with vertex set V ( G ) V(G) , a labeling ϕ : V ( G ) → { 1 , … , k } \phi\colon V(G)\to\{1,\ldots,k\} is an S S -packing k k -coloring if, whenever two distinct vertices u , v ∈ V ( G ) u,v\in V(G) are assigned the same color i i , their distance in G G is greater than s i s_{i} . The minimum k k for which G G admits such a coloring is the S S -packing chromatic number of G G . A graph G G is χ S \chi_{S} -vertex-critical if χ S ( G − v ) < χ S ( G ) \chi_{S}(G-v)<\chi_{S}(G) for every v ∈ V ( G ) v\in V(G) , and it is χ S \chi_{S} -critical if χ S ( H ) < χ S ( G ) \chi_{S}(H)<\chi_{S}(G) holds for every proper subgraph H H of G G . In this paper, the exact value of χ S ( P n ) \chi_{S}(P_{n}) is determined for every path of order n n and for every packing sequence S S where s i < 2 i s_{i}<2^{i} holds for each entry s i s_{i} . As a consequence, χ S \chi_{S} -critical and χ S \chi_{S} -vertex-critical paths are identified for each such sequence S S . In addition, we extend earlier results on χ S \chi_{S} -critical cycles and provide a complete characterization of χ S \chi_{S} -critical and χ S \chi_{S} -vertex-critical cycles for packing sequences S = ( 1 , s 2 , … ) S=(1,s_{2},\dots) with s 2 ∈ { 2 , 3 } s_{2}\in\{2,3\} and s 3 , s 4 ∈ { 4 , 5 , 6 , 7 } s_{3},s_{4}\in\{4,5,6,7\} . a Department of Mathematics, Faculty of Science, Ege University, İzmir, Türkiye b Faculty of Mathematics and Physics, University of Ljubljana, Slovenia c Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia d Department of Computer Engineering, Gebze Technical University, Türkiye e Department of Mathematics, Gebze Technical University, Türkiye Keywords: packing coloring; S -packing coloring; S -packing chromatic critical graph; cycle graph; path graph AMS Subj. Class. (2020) : 05C15, 05C12 1 Introduction A packing sequence S=(s_{1},s_{2},\ldots) is a non-decreasing sequence of positive integers. Consider a graph G with vertex set V(G) . A labeling \phi\colon V(G)\to[k]=\{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 satisfies d_{G}(u,v)>s_{i} . The minimum k for which G admits such a coloring is the S -packing chromatic number of G , denoted by \chi_{S}(G) [ 9 ] . The notion of S -packing coloring is very general. In particular, when S=(k,k,\ldots) , one obtains the class of k -distance colorings [ 15 ] , where k=1 coincides with the classical graph coloring. Furthermore, taking S=(1,2,3,\ldots) yields the standard packing coloring [ 8 , 4 ] . In recent years, the concept of S -packing coloring has drawn considerable attention [ 2 , 5 , 6 , 10 , 14 , 16 , 17 , 19 , 18 , 21 ] . Several works in the literature have investigated criticality in packing colorings [ 13 , 3 , 7 ] . As packing colorings have been generalized to S -packing colorings, the notion of criticality has also been extended to S -packing colorings. In particular, vertex criticality in S -packing coloring was introduced by Holub et al. [ 11 ] , where a graph G is \chi_{S} -vertex-critical if \chi_{S}(G-v)<\chi_{S}(G) for every v\in V(G) . Later, a characterization of \chi_{S} -vertex-critical graphs with \chi_{S}(G)=4 for a family of packing sequences was provided by Klavžar et al. [ 12 ] . Recently, criticality in S -packing coloring was introduced in [ 1 ] , where a graph G is called \chi_{S} -critical if \chi_{S}(H)<\chi_{S}(G) for every proper subgraph H of G . In the same paper, \chi_{S} -critical cycles were characterized under different conditions, and the remaining cases were left as an open problem. In this paper, among other results, we address this problem and obtain characterizations of \chi_{S} -critical cycles for several cases. 1.1 Terminology Let G=(V(G),E(G)) be a graph, where V(G) and E(G) correspond to the vertex and edge set of G , respectively. The distance between two vertices u and v in G is denoted by d_{G}(u,v) . Let P_{n} and C_{n} stand for the path and the cycle of order n , respectively. The set of all packing sequences is denoted by \mathcal{S}=\{(s_{1},s_{2},...):s_{1}\leq s_{2}\leq...\} . Throughout this paper, we assume that all packing sequences are infinite. The notation {\cal S}_{a_{1},\ldots,a_{i-1},\,\overline{a_{i}},\,a_{i+1},\ldots} stands for the set of packing sequences (s_{1},s_{2},\ldots) satisfying s_{j}=a_{j} for j\neq i and a_{i}\leq s_{i}\leq a_{i+1} . For example, {\cal S}_{1,2,\overline{4},7} is the set of packing sequences with s_{1}=1 , s_{2}=2 , 4\leq s_{3}\leq 7 , and s_{4}=7 . Note that {\cal S}_{1} is the set of all packing sequences (s_{1},s_{2},\ldots) with s_{1}=1 . Next, we introduce the following family of packing sequences. For an integer k\geq 2 , let us define {\cal S}(k)=\{(s_{1},s_{2},\dots)\colon 2^{i-1}\leq s_{i}<2^{i}\mbox{ for all }i\leq k-1\mbox{ and }s_{k}<2^{k-1}\}. (1) Then {\cal S}(1) is not defined, and {\cal S}(2)={\cal S}_{1,1} . In general {\cal S}(k)\subseteq{\cal S}_{1} . The following observation follows directly from the definition and will be used in the sequel. Observation 1.1 . If S=(s_{1},s_{2},\dots) and S^{\prime}=(s_{1}^{\prime},s_{2}^{\prime},\dots) are two packing sequences such that s_{i}\leq s_{i}^{\prime} for every positive integer i , then \chi_{S}(G)\leq\chi_{S^{\prime}}(G) holds for every graph G . 1.2 Summary of results The earlier studies left open the problem of determining the S -packing chromatic number of paths except when S belongs to a very specific subfamily of {\cal S} . In [ 1 ] , this question was posed directly. In this paper, we determine \chi_{S}(P_{n}) for all packing sequences S=(s_{1},s_{2},\dots) where the entries are not too large. More precisely, we consider all sequences where s_{i}<2^{i} holds for each i\leq\lfloor\log_{2}(n)\rfloor+1 . Theorems 3.1 and 3.3 (ii) can be summarized in the following way. If S=(s_{1},s_{2},\dots) and 2^{i-1}\leq s_{i}<2^{i} holds for each i\leq\lfloor\log_{2}(n)\rfloor+1 , then \chi_{S}(P_{n})=\lfloor\log_{2}(n)\rfloor+1. Otherwise, S\in{\cal S}(k) for an integer k\leq\lfloor\log_{2}(n)\rfloor+1 , and \chi_{S}(P_{n})=k . Based on these results, we identify \chi_{S} -critical and \chi_{S} -vertex-critical paths for the considered packing sequences. In particular, we show that if S\in{\cal S}(k) , then a path P_{n} is \chi_{S} -critical (and \chi_{S} -vertex-critical) if and only if n\in\{2^{0},2^{1},\dots,2^{k-1}\} . In [ 1 ] , \chi_{S} -critical cycles were identified for the following families of packing sequences. Theorem 1.2 . [ 1 ] If n\geq 3 , then the following hold. (i) If S\in\mathcal{S}_{1,1} , then C_{n} is \chi_{S} -critical if and only if n is odd. (ii) If S\in\mathcal{S}_{1,2,2} , then C_{n} is \chi_{S} -critical if and only if n\in\{3,5\} . (iii) If S\in\mathcal{S}_{1,\overline{2},3} , then C_{n} is \chi_{S} -critical if and only if n\not\equiv