On the Complexity of the Circular Chromatic Number
<|reference_start|>On the Complexity of the Circular Chromatic Number: 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}$.<|reference_end|>
@article{hatami2006on,
    title={On the Complexity of the Circular Chromatic Number},
    author={Hamed Hatami and Ruzbeh Tusserkani},
    journal={Journal of Graph Theory. 47(3) (2004) pp. 226-230},
    year={2006},
    archivePrefix={arXiv},
    eprint={cs/0701007},
    primaryClass={cs.CG}
}