# 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? Jun 13, 2011 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$). Jun 13, 2011 at 14:01
• @ShreevatsaR Thanks a lot! I understand the question now--unfortunately, I have no developed ideas about how to solve it. Jun 13, 2011 at 22:00