# Coloring a 3-colorable graph with $O(\sqrt{n})$ colors in polynomial time

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?

-
I'm confused by this question. My understanding is that $O(\sqrt n)$ is an algorithm complexity, not a number. I don't know what a $O(\sqrt n)$ coloring is. Do you want to three-color the graph in $O(\sqrt n)$ time or do you want to color the graph with $\sqrt n$ colors? –  Charlie Suer Jun 13 '11 at 12:59
@Charlie: Please look up Big O notation (probably there are related questions here on math.SE). The notation indicates (a class of) functions with a certain growth rate. The function may be the time complexity of an algorithm as a function of its input size, but it may also be just any function. In particular, $O(\sqrt n)$ means any function $f(n)$ such that for some constant $c$, for sufficiently large $n$, $f(n) < c\sqrt n$. Here the OP wants an algorithm which for sufficiently large n uses less than $c\sqrt n$ colours (for some fixed $c$). –  ShreevatsaR Jun 13 '11 at 14:01
@ShreevatsaR Thanks a lot! I understand the question now--unfortunately, I have no developed ideas about how to solve it. –  Charlie Suer Jun 13 '11 at 22:00

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.

-