A graph coloring algorithm makes an assignment of colors to the vertices of a graph so that each vertex is of a different color than its neighbors. The chromatic number of a graph is the least number of colors for which such an assignment can be made. The performance guarantee of a graph coloring algorithm is the worst case ratio between the number of colors it assigns to a graph and that graph’s chromatic number. In 1974, Johnson [1] showed that the Greedy Independent Set algorithm for coloring ran in time O(n²) with performance guarantee O(n/log n) for all graphs. Wigderson improves upon the results of Johnson in several ways.

First, an algorithm is given that colors any graph on n vertices with known chromatic number k in linear time with at most 2k :9I colors. This algorithm is extended and combined with the Greedy Independent Set algorithm to produce an algorithm running in O(n²) time with performance guarantee of O(n(log log n)²/(log n)²).