$S$-Packing Coloring of Cubic Halin Graphs

Abstract

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 the vertex set of $G$ 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$ and $v$ in $V_i$ is at least $s_i+1$. In this paper, we study the problem of $S$-packing coloring of cubic Halin graphs, and we prove that every cubic Halin graph is $(1,1,2,3)$-packing colorable. In addition, we prove that such graphs are $(1,2,2,2,2,2)$-packing colorable.

9 pages