Better Coloring of 3-Colorable Graphs

We consider the problem of coloring a 3-colorable graph in polynomial time using as few colors as possible. This is one of the most challenging problems in graph algorithms. In this paper using Blum's notion of "progress", we develop a new combinatorial algorithm for the following: Given any 3-colorable graph with minimum degree ∆ > √ n, we can, in polynomial time, make progress towards a k-coloring for some k = n/∆ • n o(1) .

We balance our main result with the best-known semi-definite(SDP) approach which we use for degrees below n 0.605073 . As a result, we show that O(n 0.19747 ) colors suffice for coloring 3-colorable graphs. This improves on the previous best bound of O(n 0.19996 ) by Kawarabayashi and Thorup [20].