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.
No takes yet. Share an insight, caveat, or question.
Garey et al. (1980) studied this question.
Synapse has enriched 3 closely related papers on similar clinical questions. Consider them for comparative context: