What is the chromatic number of the following graph? [The figure is a 3 x 3 grid of 9 vertices with the usual horizontal and vertical grid edges, plus one extra curved edge that arcs over the top and down the right side joining the top-left corner vertex to the bottom-right corner vertex.] A. 2 B. 3 C. 4 D. 5
GATE 2008 · Discrete Mathematics · Graph Coloring · medium
Answer: chi(G) = 3 => option B
- Two colours fail because of the arc: Colour the grid by parity: vertex (r,c) gets colour (r+c) mod 2. Then (0,0) and (2,2) both get colour 0. The extra arc joins (0,0) to (2,2); together with any grid path between them (length 4, even) it forms a cycle of odd total length 5, so the graph is not bipartite and chi >= 3.
- Three colours are enough: Keep the parity colouring (colours 1 and 2) for the eight vertices other than (2,2), and give the bottom-right corner (2,2) a new colour 3. Now every grid edge still has differently coloured endpoints, and the arc (0,0)-(2,2) joins colour 1 to colour 3. All edges are properly coloured with 3 colours, so chi <= 3.
- Combine the bounds: The two bounds pin the chromatic number to exactly 3, which is option B.