On the complexity of the circular chromatic number

DOI10.1002/jgt.20022zbMath1055.05054arXivcs/0701007OpenAlexW2952246384MaRDI QIDQ3159379

R. Tusserkani, Hamed Hatami

Publication date: 16 February 2005

Published in: Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/cs/0701007

zbMATH Keywords

circular chromatic numberNP-hard

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Related Items (5)

Circular coloring of graphs via linear programming and tabu search ⋮ On the computational complexity of defining sets ⋮ Circular chromatic number of induced subgraphs of Kneser graphs ⋮ On the restricted homomorphism problem ⋮ Describing hereditary properties by forbidden circular orderings

This page was built for publication: On the complexity of the circular chromatic number