3
$\begingroup$

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?

  • 0
    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?2011-06-13
  • 1
    @Charlie: Please look up [Big O notation](http://en.wikipedia.org/wiki/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$).2011-06-13
  • 0
    @ShreevatsaR Thanks a lot! I understand the question now--unfortunately, I have no developed ideas about how to solve it.2011-06-13

1 Answers 1

2

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.