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.