The Complexity of Coloring Circular Arcs and Chords

Authors: M. R. Garey, David S. Johnson, Gerald L. Miller, Christos H. Papadimitriou - SIAM Journal on Algebraic and Discrete Methods 1980 cited by 391

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.