October 4, 2023
GATE 2016 [Set-1]
October 4, 2023
October 4, 2023
GATE 2016 [Set-1]
October 4, 2023

GATE 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?
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.
Correct Answer: B
0 0 votes
Article Rating
Subscribe
Notify of
0 Comments
Inline Feedbacks
View all comments
0
Would love your thoughts, please comment.x
()
x
error: Alert: Content selection is disabled!!