Map Colouring Problem

The Map Colouring problem asks if it is possible to colour an area (such as a geographical map) consisting of divided regions, such that no neighbouring regions share the same colour. It is reduces to thegraph colouring problem

%%🖋 Edit in Excalidraw, and the dark exported image%%

Problem Description(s) §

Decision Version: §

Given a plane separated into $n$ discrete contiguous\ regions, can each region be assigned an element $c_i$ from a discrete set $C$ (equivalently, coloured) such that adjacent regions have different $c_i$’s (different colours)

• Contiguous: A connected, open subset of the plane (#tosee why open?):
  • Contiguous here means that we cannot call two non-connecting regions to be the same region. If they connect, they must be the same region.
• Adjacent: Sharing non-isolated boundary points
  • This is to prevent regions that only share a single point to be considered as ‘adjacent’. If we did not have this restriction, a pie-chart could have infinitely many connected regions.

Proved true by for all $n$ by the Four Colour Theorem

Optimisation Version: §

Given a plane separated into $n$ discrete contiguous regions, where each region is assigned an element $c_i$ from a discrete set $C$ (equivalently, coloured) such that adjacent regions have different $c_i$’s (different colours), what is the minimum size of $C$ (i.e. no. of colours) required?

Reduction To Graph Colouring Problem §

Every map can consisting of $n$ regions can be transformed into a planar graph containing $n+1$ nodes, with one extra node used to represent the ‘exterior’.

%%🖋 Edit in Excalidraw, and the dark exported image%%

Then the decision problem is a very restricted case of the decision version of the graph colouring problem (where we restrict ourselves to planar graphs).

More importantly, the optimisation version is the same as finding the chromatic number (minimum number of colours required) for the associated planar graph.