GATE 2023 CS – Question 55
Let G be a simple, finite, undirected graph with vertex set $\{v_1,\ldots,v_n\}$. Let $\Delta(G)$ denote the maximum degree of G and let $N = \{1, 2, \ldots\}$ 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 ∈ N : no neighbour of $v_i$ is colored j}. Which of the following statements is/are TRUE?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (A) This procedure results in a proper vertex coloring of G.; (B) The number of colors used is at most $\Delta(G)+1$.
Explanation
The greedy algorithm colours $v_i$ with the smallest colour not used by any of its **earlier-coloured** neighbours.
- **(A) True.** Each vertex avoids the colours of its neighbours, so adjacent vertices never share a colour. The colouring is proper.
- **(B) True.** A vertex has at most $\Delta(G)$ neighbours, so at most $\Delta(G)$ colours are forbidden. Among the colours $1,\dots,\Delta(G)+1$ at least one is free, so no more than $\Delta(G)+1$ colours are used.
- **(C) False.** A complete graph $K_n$ has $\Delta=n-1$ but needs $n=\Delta+1$ colours.
- **(D) False.** Greedy colouring can use more colours than the chromatic number (the number depends on the vertex order).
Answer: A, B.
More Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) questions
- GATE 2022 CS Q30
- GATE 2022 CS Q37
- GATE 2022 CS Q50
- GATE 2022 CS Q52
- GATE 2022 CS Q58
- GATE 2021 CS (CS1) Q26
All Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) questions →