Coloring k-colorable graphs using relatively small palettes

Eran Halperin, Ram Nathaniel, Uri Zwick

We obtain the following new coloring results: * A 3-colorable graph on $n$ vertices with maximum degree~$\Delta$ can be colored, in polynomial time, using $O((Δ\logΔ)^{1/3} \cdot\log{n}…