Sign up ×

I want to show the following:

If a graph $G$ has $O(|V|)$ edges, then we can color $G$ with $O(\sqrt{|V|})$ colors.

I tried to use induction on number of nodes and number of edges, but neither could lead to the conclusion.

Here's an definition of vertex coloring.

share|cite|improve this question

1 Answer 1

up vote 2 down vote accepted

Run the greedy algorithm. When color $n$ is used for the first time, to color a vertex $v$, mark the edges joining $v$ to vertices already colored (of which there will be at least $n-1$).

Every marked edge is marked only once during the process and at least $0 + 1 + \dots (c-1) = c(c-1)/2$ edges will be marked where $c$ is the number of colors used. Therefore, if $c$ colors are required there will be at least $c(c-1)/2$ edges in the graph. This bound is attained for a complete graph on $c$ vertices.

share|cite|improve this answer
What exactly is the greedy algorithm? Pick the highest degree node? – Srivatsan Sep 4 '11 at 21:16
Color the vertices one by one. At each vertex, choose the best (in this case, lowest-numbered) color satisfying the requirements. It is "greedy" in the sense that an optimal local choice is always made, whether or not that is the best choice for reducing the number of colors in the whole graph. (see ) – zyx Sep 4 '11 at 21:19
Oh, I see. Thanks. I know what greedy algorithms are in general, I wanted to know what happens in your proof. – Srivatsan Sep 4 '11 at 21:22
This is the greedy algorithm for vertex coloring : – ablmf Sep 5 '11 at 1:34

Your Answer


