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

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.

Review text

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.

Recommendations

Cites work

Cited in

(7)

This page was built for publication: A polynomial time algorithm to find the star chromatic index of trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2223458)