An O(n0.4)-approximation algorithm for 3-coloring

This paper presents a polynomial-time algorithm to color any 3-colorable n-node graph with O(n2/5 log8/5 n) colors, improving the best previously known bound of O(√n/√logn) colors. By reducing the number of colors needed to color a 3-colorable graph, the algorithm also improves the bound for k-coloring for fixed k ≥ 3 from the previous O((n/log n)1-1/(k-1)) colors to O(n1-1/(k-4/3) log8/5 n) colors. An extension of the algorithm further improves the bounds. Precise values appear in a table at the end of this paper.