2025/12/28 by Zhang, Xin, Zou, Dezhi
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2512.22809
Motivated by frequency assignment problems in wireless broadcast networks, Goddard, Hedetniemi, Hedetniemi, Harris, and Rall introduced the notion of S-packing coloring in 2008. Given a non-decreasing sequence S = (s1, s2, …, sk) of positive integers, an S-packing coloring of a graph G is a partition of its vertex set into k subsets \V1, V2, …, Vk\ such that for each 1 ≤ i ≤ k, the distance between any two distinct vertices u, v ∈ Vi is at least si + 1. In this paper, we study the S-packing coloring problem for Halin graphs with maximum degree Δ≤ 5. Specifically, we present a linear-time algorithm that constructs a (1,1,2,2,2)-packing coloring for any Halin graph satisfying Δ≤ 5. It is worth noting that there are Halin graphs that are not (1,2,2,2)-packing colorable.