GATE CS 2023 (Forenoon) — Question 55

Discrete MathematicsAdvanced Graph Bounds (Matching, Coloring Theorems)MSQ2 marksMedium

Let \(G\) be a simple, finite, undirected graph with vertex set \(\{v_1, \dots, v_n\}\). Let \(\Delta(G)\) denote the maximum degree of \(G\) and let \(N = \{1, 2, \dots\}\) denote the set of all possible colors. Color the vertices of \(G\) using the following greedy strategy:
code
1for i = 1, ..., n
2    color(v_i) <- min{j \in N : no neighbour of v_i is colored j}
3
Which of the following statements is/are TRUE?
  1. A
    This procedure results in a proper vertex coloring of \(G\).
  2. B
    The number of colors used is at most \(\Delta(G) + 1\).
  3. C
    The number of colors used is at most \(\Delta(G)\).
  4. D
    The number of colors used is equal to the chromatic number of \(G\).
Practise the full 2023-FN paper
Challenge a friend: WhatsApp Telegram
From RENYXERAPractise this subject in the exam simulatorTimed, GATE-style tests with analytics that find your weak topics.
Practise more on Advanced Graph Bounds (Matching, Coloring Theorems)Timed, in the real exam interface · free to start

A GATE question every morning

One real past-paper question every morning for your branch, answer hidden until you tap. Free on Telegram.

Join
Stuck? Ask in the student group