Impact of local girth on the S S -packing coloring of k k -saturated subcubic graphs
Ayman El Zein, Maidoun Mortada · 2026
Read Impact of local girth on the S S -packing coloring of k k -saturated subcubic graphs by Ayman El Zein, Maidoun Mortada (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-2603-25113.txt.
Introduction
El Zein and Mortada study how local cycle length shapes packing colorings of sparse cubic graphs. In an S-packing coloring, same-color vertices must sit farther apart than their color value allows. They focus on subcubic graphs where degree-3 vertices touch few peers of the same degree. Local girth gives the shortest cycle through a vertex. The pair shows how saturation and local girth jointly fix which packing sequences work. Sharp examples prove the bounds are tight. Open cases are listed for later work.
Catalog record
| CREATOR | Ayman El Zein, Maidoun Mortada |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 80073 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.25113
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Impact of local girth on the S S -packing coloring of k k -saturated subcubic graphs Ayman El Zein, Maidoun Mortada Abstract For a non-decreasing sequence S = ( s 1 , s 2 , … , s k ) S=(s_{1},s_{2},\dots,s_{k}) , an S S -packing coloring of a graph G G is a vertex coloring using the colors s 1 , s 2 , … , s k s_{1},s_{2},\dots,s_{k} such that any two vertices assigned the same color s i s_{i} are at distance greater than s i s_{i} . A subcubic graph is said to be k k -saturated, for 0 ≤ k ≤ 3 0\leq k\leq 3 , if every vertex of degree 3 is adjacent to at most k k vertices of degree 3. The local girth of a vertex is the length of the smallest cycle containing it. Brešar, Kuenzel, and Rall [ Discrete Math. 348(8) (2025), 114477] proved that every claw-free cubic graph is ( 1 , 1 , 2 , 2 ) (1,1,2,2) -packing colorable, confirming the conjecture for this family. Equivalently, a claw-free cubic graph is one in which each 3 3 -vertex has local girth 3. Motivated by this observation and by recent progress on S S -packing colorings of k k -saturated subcubic graphs, we study the influence of local girth on their S S -packing colorability. We establish a series of results describing how the parameters of saturation and local girth jointly determine the admissible S S -packing sequences. Sharpness is verified through explicit constructions, and several open problems are posed to delineate the remaining cases. Mathematics Subject Classification: 05C15 Keywords : graph, coloring, S -packing coloring, subcubic graph, local girth. 1 Introduction All graphs considered in this paper are finite, simple, and undirected. For a graph G , we denote by V(G) and E(G) its vertex and edge sets, respectively. For a vertex x\in V(G) , we denote by N(x) the set of the neighbors of x and by N_{2}(x) the set of vertices at distance exactly two from x . For a subset X\subseteq V(G) , we write N[X]=X\cup N(X) for the closed neighborhood of X . The degree of a vertex x is denoted by d_{G}(x) (or simply d(x) ), and we write \Delta(G) and \delta(G) for the maximum and minimum degrees of G . A vertex v with d(v)=k is called a k -vertex . A graph G is said to be subcubic if \Delta(G)\leq 3 and cubic if d_{G}(v)=3 for every vertex v . A subcubic graph is said to be k -saturated , for 0\leq k\leq 3 , if every vertex of degree 3 is adjacent to at most k vertices of degree 3. Equivalently, a 3 -vertex in a k -saturated graph has at least 3-k neighbors of degree 2. In a 3-saturated subcubic graph, we call a 3-vertex heavy if all its neighbors are 3-vertices. A 3 -saturated subcubic graph is said to be (3,k) -saturated , for 0\leq k\leq 3 , if each heavy vertex is adjacent to at most k heavy vertices. This classification, introduced in [ 15 , 16 ] , provides a natural hierarchy of subcubic graphs according to the density of adjacent 3 -vertices and will serve as one of the structural parameters in our analysis. A chord in a cycle is an edge joining two vertices that are not adjacent on the cycle. Given a non-decreasing sequence of positive integers S=(s_{1},s_{2},\ldots,s_{k}) , an S -packing coloring of a graph G is a partition of V(G) into subsets V_{1},V_{2},\ldots,V_{k} such that for any two distinct vertices u,v\in V_{i} , we have dist_{G}(u,v)>s_{i} . The concept, introduced by Goddard et al. [ 9 ] , has since inspired intensive research, particularly on graphs of maximum degree three (see the survey [ 2 ] ). The smallest integer k such that G admits a (1,2,\ldots,k) -packing coloring is called the packing chromatic number of G , denoted \chi_{\rho}(G) . This parameter was introduced by Goddard et al. [ 9 ] under the name broadcast chromatic number , who showed that deciding whether \chi_{\rho}(G)\leq 4 is NP-hard. The study of bounding \chi_{\rho}(G) and \chi_{\rho}(S(G)) , where S(G) denotes the graph obtained from G by subdividing every edge, has been the subject of many works [ 1 , 3 , 4 , 8 , 11 , 19 ] . The question of whether \chi_{\rho} is bounded for subcubic graphs was answered negatively by Balogh, Kostochka, and Liu [ 1 ] , with explicit unbounded constructions later provided in [ 2 ] . However, Balogh, Kostochka, and Liu [ 1 ] proved that \chi_{\rho}(S(G))\leq 8 for every subcubic graph G , while Gastineau and Togni [ 8 ] raised the question of whether \chi_{\rho}(S(G))\leq 5 . This conjecture was later supported by Brešar et al. [ 4 ] , who proposed that \chi_{\rho}(S(G))\leq 5 holds for all subcubic graphs. Moreover, Gastineau and Togni [ 19 ] observed that if a subcubic graph G is (1,1,2,2) -packing colorable, then it satisfies \chi_{\rho}(S(G))\leq 5 . Several significant results have been obtained on the S -packing coloring of subcubic graphs. It was recently shown in [ 13 ] that every subcubic graph G admits a (1,1,2,2,3) -packing coloring, which implies the general upper bound \chi_{\rho}(S(G))\leq 6 for this class. Later, El Zein and Mortada [ 6 ] proved that every subcubic graph with minimum degree less than three is (1,1,2,2) -packing colorable, confirming that shorter S -sequences suffice in the subcubic case. Their work also established that every connected cubic graph admits a (1,1,2,2,k) -packing coloring in which at most one vertex receives color k , for any k\geq 3 , thereby improving the result of [ 13 ] . This line of research continues and unifies earlier contributions by Mortada and Togni, who introduced and systematically developed the study of S -packing colorings of k -saturated subcubic graphs [ 15 , 16 , 17 , 18 ] , as well as by Mortada and El Zein [ 14 ] , whose recent work further refined the saturation framework. The present paper builds upon these foundations, combining the saturation-based perspective with the newly introduced local girth parameter to obtain a unified theory of S -packing colorability. Subsequently, Brešar, Kuenzel, and Rall [ 5 ] showed that every claw-free cubic graph is (1,1,2,2) -packing colorable. Their result, obtained through a detailed structural decomposition, revealed the importance of local restrictions in achieving compact S -packings and inspired the present investigation. The notion of local girth provides a natural parameter for describing the local cyclic structure of a vertex. For a vertex v , its local girth, denoted g(v) , is the length of the shortest cycle containing v , and it is supposed to be \infty if v belongs to no cycle. A claw-free cubic graph is precisely a cubic graph in which every vertex has local girth 3. Consequently, Brešar, Kuenzel, and Rall [ 5 ] admits a natural reformulation in terms of local girth : Every cubic graph in which every vertex has local girth 3 is (1,1,2,2) -packing colorable. Motivated by this characterization, El Zein and Mortada [ 7 ] proved that every