Improving the performance guarantee for approximate graph coloring
Avi Wigderson · Journal of the ACM · 1983
The performance guarantee of a graph coloring algorithm is the worst case ratio between the number of colors it uses on the input graph and the chromauc number of this graph.The previous best known polynomial-time algorithm had a performance guarantee O(n/logn) for graphs on n vertices.This result stood unchallenged for eight years.This paper presents an efficient algorithm with performance guarantee of O(n(loglog n)2/(logn)2).