October 4, 2023
GATE 2016 [Set-1]
October 4, 2023GATE 2023
|
Question 55
|
Let G be a simple, finite, undirected graph with vertex set {v1,…,vn}. 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(vi) ← min{j ε N : no neighbour of vi is colored j}
Which of the following statements is/are TRUE?
color(vi) ← 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