If we have a graph with a vertex-set V (finite and non-empty), and edge-set E, we can define this graph as G = (V,E). A k-colouring of G is some way of assigning k colours to the vertices of G, such that adjacent vertices (i.e. those linked by some edge) have distinct colours. Therefore, the k-colouring is a function, f: V -> K, where K is a set of k colours such that f(u) != f(v) for all edges uv in G.
We define the k-colouring problem, kC, as given any graph G, is there a k-colouring of G? Let us take a look at some algorithms to solve the kC problem.
1-Colouring Problem
The 1-colouring problem is trivial, since a graph is 1-colourable iff it is a graph with no edges.
2-Colouring Problem
2C is solvable. We assume that K = {B,W}, denoting the set of colours black and white. Taking any vertex of the graph, v, we colour v black w.l.o.g. We are then forced to colour all neighbours of v white, then their neighbours black, and so on until the whole graph is coloured. If, at any stage, we must colour a previously-coloured vertex with a different colour, then G cannot be 2-coloured. Alternatively, if we find that the entire graph G can be coloured without this situation arising, then we have a 2-colouring of G.
If V = N, the algorithm must consider N vertices, each with at most N – 1 neighbours. Therefore, the algorithm has a running time O(N2).
3-Colouring Problem
3C is solvable, but harder than 2C. We adapt the algorithm for 2C to work for 3C, but at each step, if we have just coloured a vertex with valency r (i.e. incident with r edges), we then have to consider 2r colourings over all of its r neighbours (using the two remaining colours). Therefore, we have a significantly larger number of cases to check than with the 2C problem.
If V = N in this case, we have to consider 3N functions f: V -> K in turn, and test each for the condition f(u) != f(v) for all uv in E. Thus, the running time for 3C is O(3N).