“School of Computer Science”
Back to Papers HomeBack to Papers of School of Computer Science
| Paper IPM / Computer Science / 10946 |
|
||||
| Abstract: | |||||
|
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?=?2 and n?=?3, for a given graph G with ?(G)?=?n, it is NP-complete to verify if χc(G) ≤ n− 1/k. � 2004 Wiley Periodicals, Inc. J Graph Theory 47: 226�230, 2004
Download TeX format |
|||||
| back to top | |||||
