Let G be a simple, finite, undirected graph with vertex set {v_1, v_2, ..., v_n}. Let Delta(G) denote the maximum degree...

Question

Let G be a simple, finite, undirected graph with vertex set {v_1, v_2, ..., v_n}. Let Delta(G) denote the maximum degree of G and let C = {1, 2, ..., Delta(G) + 1} denote the set of all possible colors. Color the vertices of G using the following greedy strategy: for i = 1 to n: assign to v_i the smallest color in C not already used by any neighbor of v_i that has already been colored.

Which of the following statements is/are TRUE?

A. This procedure results in a proper coloring of G.
B. The number of colors used is at most Delta(G) + 1.
C. The number of colors used is at most Delta(G).
D. The number of colors used is equal to the chromatic number of G.

Accepted Answer

A, B The greedy colouring algorithm processes vertices in a fixed order and assigns the smallest available colour at each step. It always produces a proper colouring (A is true) because it explicitly avoids colours used by already-coloured neighbours. It uses at most Delta+1 colours (B is true) because any vertex has at most Delta already-coloured neighbours, so at most Delta colours are forbidden, and the smallest available colour from {1,...,Delta+1} is always at most Delta+1. However, greedy may use more than Delta colours (C is false) and may not produce the minimum (D is false).