Packing Chromatic Numbers of Certain Unicyclic Graphs

Abstract

Packing coloring is a distance-constrained vertex coloring in which any two vertices assigned the same color i must be separated by a distance greater than i. The minimum number of colors required for such a coloring is called the packing chromatic number and is denoted by χ_ρ (G). Exact packing chromatic numbers have been determined for various graph families, including trees, cycles, graph transformations, graph products, and several other structured graph classes. Nevertheless, the packing coloring behavior of unicyclic graphs with pendant attachments remains less completely understood, particularly because the interaction between the unique cycle and the attached structures may alter the relevant distance constraints. This paper determines the packing chromatic numbers of three unicyclic graph families: the Twin Double Pendant Cycle graph TDPC_n, the Jellyfish graph J_n, and the Caveman graph CV_(m,n). The graph TDPC_n is constructed from the cycle C_n by attaching four pendant vertices, with two pendant vertices incident with each of two adjacent cycle vertices. The study employs a theoretical graph-based approach in which explicit packing-coloring constructions are used to establish upper bounds, while structural and distance arguments provide the corresponding lower bounds. The results show that χ_ρ (TDPC_n)=4 for all n≥3. Moreover, χ_ρ (J_3)=3, whereas χ_ρ (J_n)=4 for all n≥4. For the Caveman graph CV_(m,n), the packing chromatic number is given by χ_ρ (CV_(m,n))=3 when L=m(n-1)≡0(mod 4) and n is odd, and χ_ρ (CV_(m,n))=4 otherwise. These exact characterizations show that packing coloring in unicyclic graphs is governed not only by the length and periodic structure of the underlying cycle, but also by the location and distribution of pendant attachments. The results provide a structural basis for further investigations of packing coloring in broader classes of cycle-based graphs.