Question

a) Prove that by correctly numbering the vertices of your graph, the greedy colouring algorithm will give you an optimal coloring. (Hint: start with an optimal coloring of G, and use it to number your vertices.) b) Does this coloring algorithm always yield an optimal result? c) What can happens when you apply this algorithm to a complete bipartite graph Knn.

Answer 1

a. As already stated in the hint, we can number of each of the vertices as follows:-

1. Get the optimal colouring of the graph.

2. For each colour c used in optimal coloring, do the following:-

3............. For each of the vertices in graph G with color c, number them in contigous sequence

4. Color the vertices in the graph in the ascending sequence of number.

In above strategy, graph will have optimal coloring because the color assigned by Greedy algorithm will be exactly as per optimal coloring

b. No this algorithm will not always yield optimal result because this algorithm solely depends upon optimal result of graph coloring, which is not available to us and hence we will not be able to get the optimal result by whimsically numbering the vertices in arbitrary way.

c. Since any bipartite graph is always 2-colorable, Greedy algorithm will give the optimal result because once one vertex in any set say SET1  is assigned color 1, then all its neightbors in other set i.e. SET2 will be assigned color 2 and after that remaining vertices in SET1 will be assigned color 1 because none of its neighbor have color 1. Hence complete bipartite graph will always be 2-colorable by this Greedy algorithm.

Please comment for any clarification.