A polynomial time algorithm to find the star chromatic index of trees (Q2223458)

A star vertex coloring of a graph is a proper vertex coloring such that every path on four vertices, including a cycle of length four, in such a graph is colored with at least three colors. Then, all the components of the subgraphs induced with vertices of any two colors contain only stars, thus the name. The star chromatic index of a graph \(G,\) denoted by \(\chi_s(G),\) is the smallest integer \(k\) for which \(G\) admits a star edge coloring with \(k\) colors. For example, the star chromatic index of the Dyck graph is 4, while its chromatic number is 2. It is known that it is NP-complete to determine whether \(\chi_s(G)= 3,\) even when \(G\) is both planar and bipartite [\textit{M. O. Albertson} et al., Electron. J. Comb. 11, No. 1, Research paper R26, 13 p. (2004; Zbl 1053.05045)]. It has also been shown that finding an optimal star coloring for a bipartite graph is NP-hard [\textit{T. F. Coleman} and \textit{J. J. Moré}, Math. Program. 28, 243--270 (1984; Zbl 0572.65029)]. In this paper, a polynomial time algorithm is presented to construct an oriented graph, a directed graph with its underlying graph being simple, based on a given out-degree sequence. This algorithm is then made use of to determine \(\chi_s(T),\) in \(O(n^4 \log n)\), for a general tree \(T\) with \(n\) vertices. A \(O(\Delta^3 \log \Delta)\) algorithm is provided to determine \(\chi_s(T)\) for those trees of diameter at most four, where \(\Delta\) is the maximum degree of \(T.\) Various formulas are also derived for \(\chi_s(T),\) for trees with diameter at most four, and caterpillars. For example, let \(T\) be a caterpillar with maximum degree \(\Delta,\) then \(\Delta \leq \chi_s(T) \leq \Delta+1,\) and \(\chi_s(T)=\Delta+1\) iff \(T\) contains two vertices of degree \(\Delta\) and their distance equals two.