Greedy colouring

Summary

Greedy colouring is a simple method that makes a colouring of a finite graph. Put the vertices in an order $v_1, v_2, \dots, v_n$, and use the colours $1, 2, 3, \dots$. For $i = 1, \dots, n$, give $v_i$ the smallest colour that no earlier neighbour of $v_i$ has.

Remarks

A vertex $v_i$ has at most $\deg(v_i)$ earlier neighbours. Thus greedy colouring uses at most $\Delta(G) + 1$ colours, where $\Delta(G)$ is the maximum degree. The number of colours depends on the order. For each graph, some order gives an optimal colouring, but such an order is hard to find in general. Greedy colouring can be done in linear time.

Explanations

L1 human

Go through the vertices one by one, and give each one the first colour that its coloured neighbours do not use. It is fast and simple, but it does not always use the least number of colours.