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