The Complexity of Coloring Circular Arcs and Chords
Michael R. Garey, David S. Johnson, Gary Lee Miller, Christos H. Papadimitriou · SIAM Journal on Algebraic and Discrete Methods · 1980
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.