The chromatic number of the following graph is _____ (The graph shown is a cycle of 7 vertices C_7 with a chord connecting two non-adjacent vertices, creating an odd cycle inside.)

GATE 2018 · Discrete Mathematics · Graph Coloring · medium

Answer: 3

1. Establish lower bound chi >= 3: The given graph contains an odd-length cycle (visible from the figure — the chord creates a triangle or odd cycle). Therefore chi >= 3.
2. Construct a valid 3-colouring: By inspection of the graph, we can assign 3 colours such that no two adjacent vertices share a colour. Since the graph has maximum degree at most 4, the greedy algorithm uses at most Delta + 1 = 5 colours, but the structure allows a 3-colouring. Explicitly colouring shows 3 colours suffice, so chi = 3.