On the Complexity of the Circular Chromatic Number

Details On the Complexity of the Circular Chromatic Number On the Complexity of the Circular Chromatic Number

2006-12-31

arxiv.org/abs/cs/0701007v1

Journal of Graph Theory. 47(3) (2004) pp. 226-230

Computer Science

Computational Geometry

Scientific paper

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}$.

Affiliated with

Also associated with

No associations

Rating

On the Complexity of the Circular Chromatic Number does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the Complexity of the Circular Chromatic Number, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Complexity of the Circular Chromatic Number will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-293937