Map Colouring

Map colouring is a problem in which you assign colours to regions—counties, in this example—so that no two regions sharing a border have the same colour. In 1852, Francis Guthrie wondered whether four colours would always be enough to colour a map. The resulting four-colour theorem states that any planar map can be coloured with at most four colours, and some maps do require all four.

This result is called the four-colour theorem. Its 1976 proof was the first major theorem proved with extensive computer assistance.

You can represent the map as a graph, with counties as vertices and shared borders as edges. Graph colouring also applies to problems such as scheduling, register allocation, and pattern matching.

Solving

As I work through a discrete-optimization course, I am learning techniques for understanding a problem's search space. Finding the chromatic number of a general graph is NP-hard, while deciding whether a graph can be coloured with a given number of colours is NP-complete.

Brute Force

The simplest approach is to try every colour assignment and return the best valid solution. Computers are great with numbers, and I want to be lazy, but the search space expands too quickly to finish in a reasonable time.

A small example with 20 vertices and three colours has 3²⁰ = 3,486,784,401 possible assignments. About 2 seconds to test them all.*

An example with 83 vertices and four colours has 4⁸³ ≈ 9.35 × 10⁴⁹ possible assignments. About 1.5 × 10³³ years to test them all.*

*Assuming a 2 GHz computer and, very optimistically, one assignment per clock cycle.

We need another way.

Pick the Most Connected

Instead of trying every combination, we can choose the order in which to colour the vertices. Start with the vertex that has the most connections, assign the lowest available colour, and move to the next vertex. Introduce a new colour only when its neighbours already use every existing colour, and continue until every vertex is coloured.

This greedy algorithm is much faster. It does not guarantee the minimum number of colours, but that trade-off can be worthwhile. On sparse graphs, its runtime can be close to linear when the vertices are already ordered.

Saturation

This method is similar to “most connected,” but it re-evaluates the next vertex after every assignment. When a vertex is coloured, its uncoloured neighbours receive an updated saturation value: the number of different colours already present among their neighbours. DSATUR selects the vertex with the highest saturation, using degree as a common tie-breaker.

Next...

It has been interesting to see how quickly these search spaces grow and why different algorithms are necessary. A good solution is often much easier to find than a provably optimal one. Local search may improve the greedy solutions further.

Thank you for reading.