Prove that the greedy algorithm always produces a colouring

Prove that the greedy algorithm always produces a colouring of the vertices of K_rn n in 2 colors (m, n 1).

Solution

The chromatic number (G) is the least k such that G is k-colourable.

In a vertex-ordering, each vertex has at most (G) earlier neighbours

First,we prove (G) (G)+1

The bound (G)+1 is the worst upper bound that greedy colouring could produce though it is optimal for complete graphs and odd cycles.

Indeed there is a vertex ordering relative to which the greedy algorithm yields an optimal colouring. If c is an optimal colouring of G, then any ordering v₁,..., v_n such that for any i < j, c(v_i) c(v _j) will be.

But there are n! possible orderings and it is difficult to fing a good one. Actually, for any k 3 it is NP complete to decide if a graph is k-colourable .Deciding if a graph is 1-colourable is easy since such a graph as no edges and deciding if a graph is 2-colourable can be done in polynomial time. Furthermore, it is NP-hard to approximate the chromatic number within |V(G)| ^₀ for some positive constant _{0 .}

However, we can easily determine if the chromatic number is equal to (G)+1 by using the brooks theorem.

So, (G) (G)+1

Now, here (G)=1, so we have

(G) 2

So,we have

2 (G) 2

This gives, (G) =2

Thus, the for the vertices it produces a clouring in 2 colors.