Greedy graph coloring algorithm 8.9

Input: Undirected graph G = <V, E>.

Output: Graph G in which every vertex v_i ÎV gets its color(v_i) so that:

- color(v_i) Î {1, 2, …, max}, max ³ c(G);

- if v_i and v_j are adjacent then color(v_i) ¹ color(v_j).

1. Choose an uncolored vertex with the maximum degree (maximum number of adjacent vertices) and label it by color 1.
2. Among all uncolored vertices, non-adjacent to the vertex with color 1, find a vertex with the maximum degree and label it by color 1;
3. Repeat step 2 until all non-adjacent vertices get color 1;
4. Repeat steps 1, 2, 3 applying consequently color 2, color 3 and so on, until each vertex gets its color.

Let us trace Algorithm 8.9on the input graph G1.

After execution of this algorithm, we can conclude that c(G1) £ 4. Also we can see that c(G1) ³ 3 because there are cycles of odd length, for example, {M,G}, {G,K}, {K,M}. What is the exact minimum number of colors (3 or 4) required by G1? Agorithm 8.9 does not give a precise answer for this question. The same is true for any other graph coloring algorithm designed so far.

If we slightly deviate from the greedy strategy of Algorithm we can get a better variant of assigning colors to vertices of G1.

Vertices of G1 are correctly colored by 3 colors. So c(G1) £ 3. The presence of cycles of odd length prompts: c(G1) ³ 3. From here it follows c(G1) = 3.

For many graphs, the above greedy algorithm finds the upper bound for the chromatic number which is equal to this number. But it cannot be guaranteed.