A Polynomial Time Algorithm to Find the Star Chromatic Index of Trees

Abstract

A star edge coloring of a graph $G$ is a proper edge coloring of $G$ such that  every path and cycle of length four in $G$  uses at least three different colors. The star chromatic index of a graph $G$ is the smallest integer $k$ for which $G$ admits a star edge coloring with $k$ colors.  In this paper,  we present a polynomial time algorithm that finds an optimum star edge coloring for every tree. We also provide some tight bounds on the star chromatic index of trees with diameter at most four, and using these bounds we find a formula for the star chromatic index of certain families of trees.