Fast algorithm for $S$-packing coloring of Halin graphs

Abstract

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=(s_1,s_2,\dots ,s_k)$ of positive integers, an $S$-packing coloring of a graph $G$ is a partition of its vertex set into $k$ subsets $\{V_1,V_2,\dots ,V_k\}$ such that for each $1\le i\le k$, the distance between any two distinct vertices $u,v\in V_i$ is at least $s_i+1$. In this paper, we study the $S$-packing coloring problem for Halin graphs with maximum degree $\hat{I}”\le 5$. Specifically, we present a linear-time algorithm that constructs a $(1,1,2,2,2)$-packing coloring for any Halin graph satisfying $\hat{I}”\le 5$. It is worth noting that there are Halin graphs that are not $(1,2,2,2)$-packing colorable.