Question

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 \(\mathbb{N}=\{1,2,\ldots\}\) denote the set of all possible colors. Color the vertices of \(G\) using the following greedy strategy: for \(i = 1, \ldots, n\), \[ \text{color}(v_i) \leftarrow \min\{j \in \mathbb{N} : \ \text{no neighbour of } v_i \text{ 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$.

Hint:

Greedy coloring always yields a proper coloring and a universal bound of $\Delta+1$ colors, but it can be suboptimal—its performance depends on the vertex order.

Answer 1

The Correct Option is A

Step 1: Properness of the greedy rule (A).
At the moment we color $v_i$, the algorithm chooses the smallest color that is not present among already colored neighbours of $v_i$. Hence $v_i$ never receives a color used by any of its neighbours. Repeating this for every $v_i$ ensures adjacent vertices get different colors $\Rightarrow$ the coloring is proper. Thus, (A) True.
Step 2: Upper bound on colors used (B).
When coloring $v_i$, it can have at most $\Delta(G)$ neighbours, so there are at most $\Delta(G)$ forbidden colors. Therefore at least one color from the set $\{1,2,\ldots,\Delta(G)+1\}$ is available. Hence the greedy algorithm uses no more than $\Delta(G)+1$ colors overall. Thus, (B) True.
Step 3: Why (C) is False.
The complete graph $K_{\Delta(G)+1}$ has $\Delta(G)=\Delta$ but requires $\Delta+1$ colors. The greedy algorithm (indeed, any proper coloring) may need $\Delta+1$ colors, contradicting the bound $\le \Delta(G)$. Hence (C) False.
Step 4: Why (D) is not guaranteed.
The greedy algorithm depends on the vertex order and can use more colors than the chromatic number. Example: a path on three vertices ordered poorly can use $3$ colors though $\chi(P_3)=2$. Therefore (D) False. \[ \boxed{\text{Correct Options: (A) and (B)}} \]