On Strong Chromatic Index of Halin Graph
Wai Chee Shiu, Phat Lam, Weng Tam · 2006
A strong k-edge-coloring of a graph G is an assignment of k colors to the edges of G in such a way that any two edges meeting at a common vertex, or being adjacent to the same edge of G, are assigned different colors. The strong chromatic index of G is the smallest number k for which G has a strong k-edge-coloring. A Halin graph is a planar graph consisting of a tree with no vertex of degree two and a cycle connecting the leaves of the tree. A caterpillar is a tree such that the removal of the leaves becomes a path. In this paper, we show that the strong chromatic index of cubic Halin graph is at most 9. That is, every cubic Halin graph is edge-decomposable into at most 9 induced matchings. Also we study the strong chromatic index of a cubic Halin graph whose tree is a caterpillar.