Map Coloring

Image by Julee Juu from Unsplash

Have you ever looked at a political map of the world and wondered how many different colors are needed to fill it in so that no two countries sharing a border have the same color?

This exact question occurred to botanist and mathematician Francis Guthrie in 1852 while trying to color a map of the counties of England. Guthrie noticed that he only needed four colors and asked his brother (a student of the famous mathematician Augustus De Morgan) whether this held true for any conceivable map.

Thus was born the Four Color Theorem, one of the most famous problems in the history of mathematics. For over a century, the brilliant minds of the era tried to prove it without success. It was not until 1976 that Kenneth Appel and Wolfgang Haken achieved the first valid mathematical proof… and they did it with the help of a computer! It became the first major computer-assisted proof in mathematics, sparking a lively philosophical debate at the time.

The theorem states that:

Any planar map divided into contiguous regions can be colored using at most four colors, in such a way that no two adjacent regions share the same color.

(Note: Two regions that only touch at a single point are not considered adjacent).

The Graph Coloring Problem

In mathematics, a map is simply a planar graph. We can represent each country or region as a node (a vertex) and draw an edge (a line) between two nodes if those two countries share a border.

From this perspective, Guthrie’s challenge becomes the classic Graph Coloring Problem, which is of huge practical importance in the real world. Beyond coloring maps, the exact same logic applies to frequency assignment in mobile network towers (to avoid signal interference), university exam scheduling, or register allocation in compiler design.

This problem can be formulated as a binary linear optimization model that minimizes the number of colors used to color a map. Do you dare to try it?

Would you like to keep exploring the world of Operations Research? Discover more posts on the topic here.