The Complexity of Coloring Circular Arcs and Chords
The Complexity of Coloring Circular Arcs and Chords
复制标题
DOI：
10.1137/0601025
复制
发表时间：
1980-06
期刊：
影响因子：
--
通讯作者：
M. Garey;David S. Johnson;G. Miller;C. Papadimitriou
中科院分区：
文献类型：
--
作者：
M. Garey;David S. Johnson;G. Miller;C. Papadimitriou
本文证明了对称群乘积的字问题、圆弧图着色问题、圆图着色问题以及几个相关问题是NP$-完全的。对于任意固定的颜色数K，证明了确定给定圆弧图是否K-可着色的问题在多项式时间内是可解的。
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.