Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
up vote 1 down vote accepted

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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