On the Complexity of the Circular Chromatic Number

Abstract

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 $\chi (G)={\chi }_c(G)$. In this paper we prove that this problem is \NP-hard even if the chromatic number of the graph is known. This answers a question of Xuding Zhu. Also we prove that for all positive integers $k\ge 2$ and $n\ge 3$, for a given graph $G$ with $\chi (G)=n$, it is \NP-complete to verify if ${\chi }_c(G)\le n-\frac{1}{k}$.