On the complexity of the circular chromatic number
Copyright policy )On the complexity of the circular chromatic number
AbstractCircular chromatic number, χcis a natural generalization of chromatic number. It is known that it isNP‐hard to determine whether or not an arbitrary graphGsatisfies χ(G)=χc(G). In this paper we prove that this problem isNP‐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 integersk ≥ 2 andn ≥ 3, for a given graphGwith χ(G) = n, it isNP‐complete to verify if$\chi _c(G) \le n- {1\over k}$. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 226–230, 2004
- Sharif University of Technology (Sharif Policy Research Institute) Iran (Islamic Republic of)
- Sharif University of Technology Iran (Islamic Republic of)
- Institute for Research in Fundamental Sciences Iran (Islamic Republic of)
circular chromatic number, Computational Geometry (cs.CG), FOS: Computer and information sciences, Coloring of graphs and hypergraphs, Computer Science - Computational Geometry, NP-hard
circular chromatic number, Computational Geometry (cs.CG), FOS: Computer and information sciences, Coloring of graphs and hypergraphs, Computer Science - Computational Geometry, NP-hard
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).6 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!