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?