Map Coloring

I'd like to use simple terms in presenting this problem, as its definition is really like that: simple and intuitive. We have a map containing some contiguous regions, we want to assign a color to each region so that non adjacent regions share the same color. Mapmakers always try to color political maps in a way to achieve clear distinction among regions, especially if they are one next to another.

After few thoughts on the previous definition, I'd like to take a further step: finding the minimum number of colors needed to color correctly any map. That is solving the previous problem for the toughest map instances possible.

Some examples of maps

Fig. 1: A sample map containing 5 regions.

In Figure 1 I assigned some colors to the regions without any particular rule but the one that states that no adjacent regions can have the same color. The number of colors used here is 4. Note that regions C and E have the same color: this is allowed since they don't have any common border. Is it possible to do better, to use less colors?

One can play around a little bit and it won't take long before he finds something like this.

Fig. 2: The same map containing 5 regions, now using 3 colors.

In Figure 2 the colors have been reduced to 3. Regions A, C and E all share the same color. Again this does not violate the only rule we are imposing on the solution. Now comes the question: is it possible to do better? Go on and try.

The answer is no, it's not possible. To understand that simply consider regions A, B and D. If we assign color 1 to A, then be must be assigned a different one since it is adjacent. So we assign color 2 to B. D is adjacent to both regions A and B, so it cannot be assigned neither color 1 nor color 2. So we can only use a third color for D.

Changing the model: graphs

The first time I was presented the problem I tried to switch to a different representation of a map, in order to make it easier to do some formal reasoning. I was natural for me to use graphs.

We represent each region with a node. We draw an edge between two nodes if they are adjacent in the map. The next figure is a representation of the previous map in terms of a graph.

Fig. 3: The graph representing the previous map.

The problem stated in this new model is the following: assign a color to each node so that each pair of nodes connected by an edge have different colors. It is obvious that to satisfy this constraint the least amount of colors that we need is 2. Now a big question...

What causes us to use more than 2 colors?

If we analyze the structure of the graph, we realize that every time we have a group of nodes that are all connected to each other we must assign a different color to each node. In Figure 3, regions A, B and D have this structure, regions B, D, E the same and B, C, D too. That's why we had to use 3 colors: these structure (they are sets of nodes) contains 3 nodes each. A set with each of its node connected to every other node is called a clique

Generalizing the previous discovery we can say that it is sufficient to find the maximum clique (the clique containing the highest number of nodes) in order to solve the problem. If the max clique has cardinality n, then n is the minimum number of colors that we need to dye the map.

Maximum number of colors for ANY geographical map

We can now proceed to find the exact number needed to color every possible geographical map. The following result holds for contiguous regions only, that is regions that do not contains islands or separated lands.

The formal notation is very helpful, but it is even too powerful: it is possible to draw graphs that do not correspond to a feasible map. Intuitively we can understand that only planar graphs represent a map. A graph is planar if it does not have edges that cross and thus can be represented on a plane. A planar graph allows a mapping of nodes to points in 2D space, in a similar way to regions. A cross of two edges would mean, translated in geographical terms, that a region passes through the border of two other regions, that is clearly impossible.

Take the example shown in the next image.

Fig. 4: Unfeasible situation.

We can now state the solution method of the problem in this way: it is sufficient to find the maximum clique possible on a planar graph to find the exact number of colors needed for every map. Since we already found a clique of cardinality 3 in the previous examples, let's try 4.

Fig. 5: Clique of cardinality 4 on a planar graph.

Figure 5 show how it is possible to have 4 nodes all connected to each other and still with no crossing edges. So 4 regions can all be connected to each other. Next image shows an example of this.

Fig. 6: Map requiring 4 colors.

It comes natural to ask: is it possible to find a bigger clique? The answer is no, since the 4-clique always puts a node/region in an unreachable state. In figure 6 region D is unreachable, that is all its borders are occupied and no new region can touch it. So a new region can be assigned color of region D, keeping 4 as the total number of needed colors.

In conclusion every map can be colored by using only 4 different colors in a way so that no adjacent region share a color.

As stated at the beginning of this article, my approach has been intuitive, so that any one could enjoy the beauty of this subject. To know more check the Four Color Theorem on Wikipedia. The generic problem associated to the simpler one presented here is the Graph Coloring.