Problem 10.1: Polynomial Graph Coloring

In the paper

U. Feige and J. Kilian, Zero knowledge and the chromatic number, Proc. 11th Annual IEEE Conf. on Computational Complexity, 1996

it is proved that unless the decision problems in the class NP have efficient randomized algorithms, then there is no polynomial time graph coloring algorithm that performs as well as described in Johnson's question. Although this would not immediately imply NP=P, it is considered a very strong negative indication of the existence of such a polynomial algorithm.

The proof of the above result uses a result on approximating the size of a maximum independent set proved in

J. Håstad, Clique is hard to approximate within n 1-ε , Proc. 37th IEEE FOCS, IEEE (1996), 627-636.

August 11, 2000, T.R. Jensen.

Back to Overview menu
Back to Graph Coloring Problems homepage

Last modified August 11, 2000 Tommy R. Jensen