On the Complexity of the Circular Chromatic Number

Hamed Hatami, Ruzbeh Tusserkani

Circular chromatic number, ${\chi }_c$ is a natural generalization of chromatic number. It is known that it is \NP-hard to determine whether or not an arbitrary graph $G$ satisfies $χ(G)…