Let G be a simple, finite, undirected graph with vertex set \v_1, , v_n\. 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:

This procedure results in a proper vertex coloring of G.

The number of colors used is at most (G) + 1.

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.

GATE CSE 2023 Q55: Greedy vertex colouring: properness and colour count

Engineering Mathematics
2 marks
MSQ
No negative marking

Let $G$ be a simple, finite, undirected graph with vertex set $\{v_1, \ldots, v_n\}$ . Let $\Delta(G)$ denote the maximum degree of $G$ and let $\mathbb{N} = \{1, 2, \ldots\}$ denote the set of all possible colors. Color the vertices of $G$ using the following greedy strategy:

for i = 1, ..., n
    color(v_i) ← min{ j ∈ N : no neighbour of v_i is colored j }

Which of the following statements is/are TRUE?

Try it: multiple select: one or more correct options

Select all correct options. No negative marking, no partial marks.

Show answer and explanation

Answer: A, B (official GATE 2023 final answer key)

Concept used: Greedy colouring: a vertex with at most $\Delta$ neighbours always finds a free colour among $\Delta + 1$ .

First step: Test C and D on small graphs, e.g. a triangle ( $\Delta = 2$ , needs 3 colours) or a path coloured in a bad order.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2023 CS question paper and final answer key, organised by IIT Kanpur. Question paper · Answer key

PracticePractise Engineering Mathematics questions →Full paperAll GATE CSE 2023 questions →

GATE CSE 2023 Q55: Greedy vertex colouring: properness and colour count

Question

Full step-by-step solution

More Engineering Mathematics PYQs