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 Graph Coloring Problems homepage