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 strongly connected to the graph colouring problem (since it can be transformed into it).

%%🖋 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 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?

Four Colour Theorem §