Premium
On the complexity of the circular chromatic number
Author(s) -
Hatami H.,
Tusserkani R.
Publication year - 2004
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20022
Subject(s) - combinatorics , mathematics , chromatic scale , graph , windmill graph , discrete mathematics , critical graph , generalization , friendship graph , graph power , line graph , mathematical analysis
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 $\chi _c(G) \le n- {1\over k}$ . © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 226–230, 2004
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom