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 [algorithm|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 [wlog|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(N²).

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(3^N).

Graph-Colouring Problem