The Complexity of Coloring Circular Arcs and Chords

Authors:
  • MGM. R. Garey
    M. R. Garey
  • DJD. S. Johnson
    D. S. Johnson
  • GMG. L. Miller
    G. L. Miller
  • CPC. H. Papadimitriou
    C. H. Papadimitriou
Publisher website
Google Scholar
Abstract
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.

This publication has 11 references indexed in Scilit: