The 15 parts of the given figure are to be painted such that no two adjacent parts with shared boundaries (excluding corners) have the same color. The minimum number of colors required is A. 2 B. 3 C. 5 D. 6

GATE 2024 · General Aptitude · Graph Coloring · medium

Answer: Minimum colors required = 2 (Option A)

1. Identify adjacency structure of the figure: The figure consists of rings divided by radial lines. Each region is adjacent to its radial neighbors and ring neighbors. Assigning Color 1 to all 'even-ring' or 'even-sector' regions and Color 2 to 'odd' ones creates a valid 2-coloring.
2. Verify 2-coloring is sufficient and necessary: Since adjacent regions must differ and there is at least one adjacency, chi >= 2. The bipartite 2-coloring works for all 15 parts, so chi = 2.