October 4, 2023
GATE 2016 [Set1]
October 4, 2023GATE 2023
Question 55

Let G be a simple, finite, undirected graph with vertex set {v_{1},…,v_{n}}. Let Δ(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 ε N : no neighbour of vi is colored j}
Which of the following statements is/are TRUE?
color(v_{i}) ← min{j ε N : no neighbour of vi is colored j}
Which of the following statements is/are TRUE?
This procedure results in a proper vertex coloring of G.


The number of colors used is at most Δ(G) + 1.


The number of colors used is at most Δ(G).


The number of colors used is equal to the chromatic number of G.

Correct Answer: B
Subscribe
Login
0 Comments