The Complexity of Coloring Circular Arcs and Chords 论文

摘要

The word problem for products of symmetric groups, the circular arc graph coloring problem, and the circle graph coloring problem, as well as several related problems, are proved to be $NP$-complete. For any fixed number K of colors, the problem of determining whether a given circular arc graph is K-colorable is shown to be solvable in polynomial time.