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?

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

1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.