4-Colouring Problem

computation graph-theory

Definition

4-Colouring Problem

The 4-colouring problem is a decision problem that asks whether the vertices of a graph can be coloured with at most four colours so that no two adjacent vertices have the same colour.

Instance: an undirected graph $G=(V,E)$

Question: Does $G$ admit a proper colouring with four colours?

NP-Membership

The 4-colouring problem is in NP.

A certificate is a colouring function

$$f:V\to \{1,2,3,4\}.$$

The verifier checks every edge $[u,v]\in E$ and accepts exactly when

$$f(u)\ne f(v).$$

This takes polynomial time in the size of the graph.

NP-Completeness

The 4-colouring problem is NP-complete. A simple proof reduces 3-colouring to 4-colouring.

Let $G=(V,E)$ be an instance of 3-colouring. Construct a graph $G^{\prime }=(V^{\prime },E^{\prime })$ by adding one new vertex $u$ and connecting it to every old vertex:

$$V^{\prime }=V\cup \{u\},E^{\prime }=E\cup \{[u,v]\mid v\in V\}.$$

The new vertex $u$ is adjacent to every old vertex. Therefore, in any valid 4-colouring of $G^{\prime }$, no old vertex may use the colour of $u$. The old vertices must then use only the remaining three colours.

Hence

$$G\text{ is 3-colourable}⟺G^{\prime }\text{ is 4-colourable}.$$

This gives a polynomial-time many-one reduction from 3-colouring to 4-colouring. Since 4-colouring is also in NP, it is NP-complete.

Planar Variant

The planar 4-colouring problem restricts the input to planar graphs.

Four Colour Theorem

Every planar graph can be coloured with at most four colours so that adjacent vertices have different colours.

Therefore, the decision version of planar 4-colouring is polynomial-time solvable: every valid planar input is a yes-instance.

This is a useful contrast with many other planar restrictions. For example, planar 3-colouring remains NP-complete, but planar 4-colouring becomes easy as a decision problem.

Relation to k-Colouring

The 4-colouring problem is the fixed-$k$ case of the k-colouring problem with $k=4$.

For unrestricted graphs, increasing from three to four colours does not make the decision problem polynomial-time solvable. For planar graphs, the fourth colour is enough to guarantee a proper colouring.