Magnús M. HalldórssonWe present an approximation algorithm for graph coloring which achieves a performance guarantee of O(n (loglog n)^2 /(log n)^3), a factor of log log n improvement.
Science Institute, University of Iceland, IS-107 Reykjavik, Iceland.