The GATE Grind

GATE 2023 CS – Question 55

Engineering Mathematics · Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) · 2 marks · Multiple select

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?

  1. This procedure results in a proper vertex coloring of G.
  2. The number of colors used is at most $\Delta(G)+1$.
  3. The number of colors used is at most $\Delta(G)$.
  4. The number of colors used is equal to the chromatic number of G.

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

Each vertex avoids its neighbours' colors, so the coloring is proper. A vertex has at most Δ neighbours, so a color in {1..Δ+1} is always free. Complete graphs need Δ+1 colors, and greedy can exceed the chromatic number.