I am considering the following problem.
You are given a graph $G$ that is 3-colorable. You would like to obtain (in polynomial time) a proper coloring for it that uses $O(\sqrt{n})$ colors .
My intuition is telling me that perhaps it is useful to consider a spanning tree $T$ of $G$. We can find a proper 2-coloring for $T$ in polynomial time. It is then only a matter of adding all the edges $E(G) \setminus E(T)$ into $T$ and recolor vertices that break the proper coloring condition. However I am not able to finish this idea and actually provide a proper $O(\sqrt{n})$ coloring.
Anyone happens to see how to solve the problem?
Best Answer
Here's a hint: when a graph is 3-colorable, the neighborhood (subgraph spanned by the neighbors) of each vertex is 2-colorable. Greedily start by coloring the neighborhoods of vertices with high degree, and throw out the parts already colored.
If you're still stuck let me know and I'll provide more details.