Graph colouring

Definition

Let $G$ be a graph with vertex set $V$, and let $C$ be a set, the set of colours. A colouring of $G$ with colours in $C$ is a function $c : V \to C$ such that $c(u) \neq c(v)$ for any two adjacent vertices $u$ and $v$.

Remarks

Such a colouring is also called proper. A colouring with a set of $k$ colours is a $k$-colouring. Each colour class $c^{-1}(x)$ is an independent set. A graph has a $2$-colouring if and only if it is bipartite. The subject started with the colouring of maps. Francis Guthrie stated the four colour conjecture in 1852.

Explanations

L1 human

Colour the vertices of a graph so that the two ends of each edge have different colours. For example, a timetable gives each exam a time slot, so that exams with a common student are at different times.