GATE 2023 CS Q.55: solution and answer

GATE 2023 · CSQ.55 · 2 marks · MSQ

Let $G$ be a simple, finite, undirected graph with vertex set ${v_{1}, \dots, v_{n}}$ . Let $Δ (G)$ denote the maximum degree of $G$ and let $N = {1, 2, \dots}$ denote the set of all possible colors. Color the vertices of $G$ using the following greedy strategy:

for $i = 1, \dots, n$

color (v_{i}) \leftarrow 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 $Δ (G) + 1$ .
(C)
The number of colors used is at most $Δ (G)$ .
(D)
The number of colors used is equal to the chromatic number of $G$ .

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

Statements (A) and (B) are TRUE; (C) and (D) are FALSE.

Official answer: A, BSource: Official answer key, GATE 2023 CS (IIT Kanpur)

The algorithm processes vertices $v_{1}, \dots, v_{n}$ in a fixed order, assigning each vertex the smallest color not already used by any of its already-colored neighbours (those earlier in the order).
(A) Properness: for any edge $(v_{i}, v_{k})$ with $i < k$ , when $v_{k}$ is colored, $v_{i}$ is already colored, so $v_{k}$ 's rule explicitly excludes $color (v_{i})$ . Hence no edge is ever monochromatic, for any vertex order — the coloring produced is always proper. (A) is TRUE.
(B) Bound $Δ (G) + 1$ : when $v_{i}$ is colored, its already-colored neighbours number at most $Δ (G)$ (its total degree bound), so at most $Δ (G)$ colors are forbidden. A color from ${1, \dots, Δ (G) + 1}$ is therefore always available, so greedy never uses more than $Δ (G) + 1$ colors. (B) is TRUE.
(C) Tightness of the $Δ (G)$ bound: take $G = K_{n}$ , so $Δ (G) = n - 1$ . Every vertex is adjacent to all others, so each new vertex needs a brand-new color: colors $1, \dots, n$ are all used, i.e. $n = Δ (G) + 1 > Δ (G)$ colors. So 'at most $Δ (G)$ ' fails in general. (C) is FALSE.
(D) Order-dependence vs. chromatic number: greedy's color count depends on the chosen vertex ordering $v_{1}, \dots, v_{n}$ . A bipartite graph (e.g. a crown graph, $K_{n, n}$ minus a perfect matching) has $χ (G) = 2$ , but a poor ordering can force greedy to use strictly more than 2 colors. Since the number of colors used is not guaranteed to equal $χ (G)$ , (D) is FALSE.
Hence the TRUE statements are exactly (A) and (B).

KEY IDEA

Sequential greedy coloring always produces a proper coloring, and it never uses more than $Δ (G) + 1$ colors — but this bound is not always tight ( $Δ (G)$ alone can fail), and the actual number of colors greedy uses depends on the vertex order, so it need not equal $χ (G)$ .

WATCH OUT FOR

Confusing the proved greedy bound $Δ (G) + 1$ with a tighter, unproven bound of $Δ (G)$ , and assuming the greedy result equals the chromatic number $χ (G)$ just because the algorithm is "optimal-looking" — the number of colors greedy uses is order-dependent and can exceed $χ (G)$ .

From the GATE 2023 CS paper. Every question of this paper · Download the full paper · All 8 Design techniques questions, with notes

GATE 2023 CS Q.55: solution and answer

Answer and solution

More Design techniques questions