Show that any graph can be properly vertex-colored with (2m)^(1/2) colors, where m is the number of edges.

Printable View

- Jul 27th 2010, 07:02 PMbeckograph vertex colouring
Show that any graph can be properly vertex-colored with (2m)^(1/2) colors, where m is the number of edges.

- Aug 2nd 2010, 01:54 AMevouga
I assume you meant ceil(sqrt(2m)). (The theorem's false if you take the floor instead.)

The key lemma to prove first is that if G is colored optimally and c1 and c2 are two different colors, then there exists an edge between a vertex colored c1 and a vertex colored c2.

Now consider an optimal coloring of G. Let c be the number of colors used. Then by the lemma there is an edge in G for each of the c(c-1)/2 possible pairs of colors, and obviously each of these edges are distinct. Thus c(c-1)/2 <= m.

Manipulating this inequality gives

sqrt(2m) >= sqrt(c(c-1))

ceil(sqrt(2m)) >= ceil(sqrt(c(c-1))) = c, as desired. - Aug 2nd 2010, 11:46 AMbecko
thanks. That solves it.