On Strong Chromatic Index of Halin Graph

Abstract

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 characteristic tree is a caterpillar.