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

CREATORAyman El Zein, Maidoun Mortada
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE80073
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

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

Read the complete text