GATE CS 2023 Set 1 — Question 55
Go beyond PYQs with Success TrackerAI-powered personalised practice and doubt support. Unlimited practice on eligible plans; AI usage limits apply.MSQ+2 / -0MediumGraph ColoringGraph Theory (Math)Engineering Mathematics
Engineering Mathematics → Graph Theory (Math) → Graph Coloring
Last updated
Question
Let be a simple, finite, undirected graph with vertex set . Let denote the maximum degree of and let denote the set of all possible colors. Color the vertices of using the following greedy strategy:Which of the following statements is/are TRUE?
for i = 1, ..., n
color(v_i) ← min{j ∈ N : no neighbour of v_i is colored j}
Correct answer
(A) This procedure results in a proper vertex coloring of G.; (B) The number of colors used is at most Δ(G) + 1.
Solution
The given procedure is the standard Greedy Coloring Algorithm.
1.Proper Coloring (Statement A): The algorithm assigns the smallest color index such that no neighbor of is already colored with . This explicitly ensures that no two adjacent vertices share the same color. Thus, it always produces a proper vertex coloring. (A is TRUE)
2.Number of Colors (Statement B): When the algorithm considers vertex , it has some number of already-colored neighbors. The number of neighbors is at most . In the worst case, all neighbors have distinct colors . Even then, the color will be available. Therefore, the algorithm never uses a color index greater than . (B is TRUE)
3.At most (Statement C): This is false. Consider a complete graph . The maximum degree is . The greedy algorithm (and any proper coloring) requires colors. Since , it is not bounded by . (C is FALSE)
4.Chromatic Number (Statement D): The number of colors used by the greedy algorithm depends heavily on the vertex ordering. While there exists an ordering that achieves the chromatic number , an arbitrary ordering (like ) does not guarantee minimality. For example, a bipartite graph () can be colored with many colors if the ordering is poor. (D is FALSE)
Continue learning with Success Tracker
A step still unclear? Work through it with support
Use Success Tracker to ask about the reasoning, then try another GATE CS question to check your understanding.
AI-powered practice· Unlimited practice on eligible plans
- PYQs with solutions
- Attempt available previous-year questions, then compare your reasoning with the worked solution. Coverage varies by stream.
- Practice that adapts
- Choose a topic, work on weaker areas and bookmark questions to revisit. Your attempts feed your progress tracking.
- AI doubt support
- Ask follow-up questions about a step or concept while practising, instead of stopping at the final answer.
Unlimited practice is available on eligible plans. Free practice and AI usage have limits; check the current plan allowances before choosing.
This page stays readable without an account. AI responses can be wrong; check them against the solution and source material.
More questions on Graph Theory (Math)
2026 Set 2 Q3A day can only be cloudy or sunny. The probability of a day being cloudy is , independent of…2026 Set 2 Q5‘When it is raining, peacocks dance.’ Based only on this sentence, which one of the following…2026 Set 2 Q8Figures (i) and (ii) represent intercity highway systems. The black dots represent cities and the…2026 Set 1 Q10An unbiased six-faced dice whose faces are marked with numbers 1, 2, 3, 4, 5, and 6 is rolled twice…2026 Set 2 Q10An unbiased six-faced dice whose faces are marked with numbers 1, 2, 3, 4, 5, and 6 is rolled twice…