Let G be a simple, finite, undirected graph with vertex set {v_1, ..., v_n}. Let Delta(G) denote the maximum degree of G and let N = {1, 2, ...} denote the set of all possible colors. Color the vertices of G using the following greedy strategy: for i = 1, ..., n: color(v_i) <- min{j in N : no neighbour of v_i is colored j}. Which of the following statements is/are TRUE? A. This procedure results in a proper vertex 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.

GATE 2023 · Discrete Mathematics · Graph Coloring · medium

Answer: Statements A and B are TRUE (answer: A, B).

1. A - it is always proper: By definition v_i takes a colour no already-coloured neighbour has; later neighbours likewise avoid v_i. So no edge is monochromatic - proper. TRUE.
2. B - at most Delta+1 colours: Each v_i has at most Delta neighbours, so at most Delta colours are blocked; among {1, ..., Delta+1} one is always free. TRUE.
3. C and D - not always true: For K_n, Delta = n-1 but n colours are needed, so C (<= Delta) is false. A bad ordering can make greedy use more than chi(G) (e.g. a crown graph), so D is false.