Packing Chromatic Number of Graph Families Constructed from the Fan Graph

Abstract

Packing coloring is particularly sensitive to graph distances, since even a simple structural modification may change whether a color can be reused. This paper investigates the packing chromatic number of several constructions derived from the fan graph, namely the subdivision fan S(F_n), the umbrella graph U_r,s, two barbell-type fan constructions, and the generalized q-fan chain CF_m(q) formed by sequentially joining the centers of q copies of F_m. The known packing chromatic number of the ordinary fan is used only as a reference result. By combining explicit packing colorings with lower bound arguments based on independence numbers, graph diameters, color class capacities, and cross-component distances, we prove that χ_ρ(S(F_n)) = 4 for n ≥ 2 and determine the exact packing chromatic numbers of the umbrella and both barbell-type constructions. For CF_m(q), we establish general lower and upper bounds for all m, q ≥ 2 by showing that a color ℓ ≥ 2 can occur on at most ⌈q/(ℓ − 1)⌉ vertices. Moreover, when m ≥ 2q − 2, the bounds coincide and yield χ_ρ(CF_m(q)) = q(⌊m/2⌋ + 2) − ∑_t=1^q−1⌈q/t⌉. These results show that the packing chromatic behavior of fan-derived graphs is governed by the distance structure created by the underlying graph operation, particularly the extent to which low colors can be reused across different fan copies.