Graph Vertex Colouring is the task of, given a graph $G,$ assigning to
each vertex of $G$ a "colour" such that for every edge $uv$ of $G,$ the
vertices $u$ and $v$ get different colours.
Given a graph $G=(V,E)$ and a set of colours $C$,
a "colouring" is a function $f:V\to C$ such that for
every $\{u,v\}\in E$, $f(u)\ne f(v)$.
If $|C|=k$ then $f$ is said to be a $k$-colouring and $G$
is said to be $k$-colourable. We observe that if $G$ is
$k$-colourable then it is $k_0$-colourable for every
$k_0\ge k$.
Given a graph, the question of whether it can be coloured using only 0,
1, or 2 colours is trivial. The question of whether a graph $G$ can be
coloured using 3 (or more) colours is NP-Complete.
