Computing the Star Chromatic Index of Every Tree in Polynomial Time
Behnaz Omoomi, Elham Roshanbin, Marzieh Vahid Dastjerdi · arXiv (Cornell University) · 2018
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 first obtain star chromatic index of every tree with a polynomial time algorithm and then we present a polynomial time algorithm that provides an optimal star edge coloring for every tree.