A Polynomial Time Algorithm to Find Star Chromatic Index on Bounded Treewidth Graphs with Given Maximum Degree
摘要
A star edge coloring of a graph G is a proper edge coloring with no 2-colored path or cycle of length four. The star edge coloring problem is to find an edge coloring of a given graph G with minimum number k of colors such that G admits a star edge coloring with k colors. This problem is known to be NP-complete. In this paper, for a bounded treewidth graph with given maximum degree, we show that it can be solved in polynomial time.