On the Complexity of the Circular Chromatic Number
| dc.creator | Hatami, Hamed | |
| dc.creator | Tusserkani, Ruzbeh | |
| dc.date | 2006-12-31 | |
| dc.date.accessioned | 2026-07-07T07:37:52Z | |
| dc.date.available | 2026-07-07T07:37:52Z | |
| dc.description | Circular chromatic number, $χ_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) = χ_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 $χ(G)=n$, it is \NP-complete to verify if $χ_c(G) \le n- \frac{1}{k}$. | |
| dc.identifier | https://arxiv.org/abs/cs/0701007 | |
| dc.identifier | http://arxiv.org/abs/cs/0701007 | |
| dc.identifier | Journal of Graph Theory. 47(3) (2004) pp. 226-230 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/120925 | |
| dc.subject | Computational Geometry | |
| dc.title | On the Complexity of the Circular Chromatic Number | |
| dc.type | text |