The colouring problem is to assign a colour to every vertex of a graph such that no two adjacent vertices have the same colour. These colours, of course, are not necessarily colours in the optic sense.

Consider the following graph:

$$\xymatrix{ A \ar@{-}[r] & B \ar@{-}[r] \ar@{-}[d] & C \ar@{-}[r] \ar@{-}[dl] & F \ar@{-}[dl] \\ & D \ar@{-}[r] & E & }$$

One potential colouring of this graph is:

$$\xymatrix{ {\color{red}A} \ar@{-}[r] & {\color{blue}B} \ar@{-}[r] \ar@{-}[d] & {\color{red}C} \ar@{-}[r] \ar@{-}[dl] & {\color{green}F} \ar@{-}[dl] \\ & {\color{green}D} \ar@{-}[r] & {\color{blue}E} & }$$

$A$ and $C$ have the same colour; $B$ and $E$ have a second colour; and $D$ and $F$ have another.

Graph colouring problems have many applications in such situations as scheduling and matching problems.