On the complexity of the circular chromatic number

Circular chromatic number, X, 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 (X)(G)= (XC)(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 greater than or equal to 2 and n greater than or equal to 3, for a given graph G with (X)(G)= n, it is NP-complete to verify if (XC)(G)less than or equal to n - 1/k. (C) 2004 Wiley Periodicals, Inc.