Chromatic number

Definition

Let $G$ be a finite graph. The chromatic number $\chi(G)$ is the smallest natural number $k$ such that $G$ is $k$-colourable.

Remarks

For the complete graph, $\chi(K_n) = n$. For the cycle graph $C_n$, $\chi(C_n)$ is $2$ if $n$ is even and $3$ if $n$ is odd. A greedy colouring shows that $\chi(G) \le \Delta(G) + 1$, where $\Delta(G)$ is the maximum degree. The chromatic number is at least the clique number.

Explanations

L1 human

The chromatic number is the least number of colours that you need to colour a graph properly. For a map, it is the least number of colours that keeps neighbouring countries in different colours.