Coloring k-colorable graphs using smaller palettes
Eran Halperin, Ram Nathaniel, Uri Zwick · 2001
We obtain the following new coloring results: A 3-colorable graph on n vertices with maximum degree can be colored, in polynomial time, using O(( log ) log n) colors. This slightly improves an O(( ) log n) bound given by Karger, Motwani and Sudan. More generally, k-colorable graphs with maximum degree can be colored, in polynomial time, using 1=k ) log n) colors.