Chromatic number
Graph theory and combinatorics
The smallest number of colours needed to colour a graph’s vertices so that no two adjacent vertices — vertices joined by an edge — share a colour.
What is usually left out
Adjacent, not connected. Under the connected reading the answer for any connected graph would just be its vertex count, which is a different and far less interesting quantity: a path on five vertices has chromatic number 2, not 5. The four colour theorem states that every planar graph has chromatic number at most 4.