The problem of coloring a graph with the fewest possible number of colors is a notoriously hard algorithmic problem. The difficulty of this problem is illustrated by the fact that if a graph on n vertices is given that is known to be 3-colorable, then there is no known polynomial time algorithm that is guaranteed to color the graph with even n^{1/4} colors! More generally, for each fixed integer k, it is natural to ask how well can a polynomial time algorithm color k-colorable graphs? The best results along this line are due to Karger, Motwani, and Sudan.
We improve the coloring results obtained by Karger, Motwani and Sudan for coloring k-colorable graphs. Specifically, we show that a 4-colorable graph on n vertices can be colored, in polynomial time, using \tilde{O}(n^{7/19}) colors, improving the \tilde{O}(n^{2/5}) bound given by Karger Motwani and Sudan. More generally, we show that k-colorable graphs on n-vertices can be colored, in polynomial time, using \tilde{O}(n^{\alpha_k}) colors, where alpha_5=97/207, alpha_6=43/79, alpha_7=1391/2315.... This result is obtained by combining the coloring algorithm of Karger, Motwani and Sudan, the combinatorial coloring algorithms of Blum and an extension of a technique of Alon and Kahale for finding relatively large independent sets in graphs that are guaranteed to have very large independent sets. The extension of the Alon and Kahale result may be of independent interest. We also show how a tighter analysis of the algorithm of Karger, Motwani and Sudan reduces a polylog factor in the number of colors needed.This is a joint work with Ram Nathaniel and Uri Zwick.