Coloring maps 1 (2)
The famous Four Color Theorem states that every map on the plane or on the sphere can be colored using at most four colors in such a way no two adjacent regions share the same color. (Each region has to be in one piece, otherwise the theorem does not hold.)
This property has been conjectured for the first time in 1852, by Francis Guthrie. (Apparently, the cartographers did not notice this property or were not interested into using just 4 colors...)
This difficult theorem has been proved only in 1976 by two American mathematicians, K.Appel e W.Haken. They reduced the general problem to a finite number of subcases and used a computer program to analyze them.
More details on this innovative proof can be found at
Mathworld
and in the book Four Colors Suffice
The theorem is valid if one knows the map in advance. But what happens if we are given the map one region at a time by a clever adversary and we must color the new region without modifying the already colored ones?
If we are really lucky we can randomly choose the colors and end up with a 4-coloring of the map. So let us imagine a more rational ("greedy") approach, that is, to use each time the first available color which does not violate the rules. (We can assume that the colors are ordered somehow.)
How bad can things go? That is, which is the largest number of colors needed in the worst case? Five? Six or seven? More?
It is easy to see that four colors do not suffice anymore:
Indeed, in the example above, we started from a green region, then we added two non-touching regions that we can paint with the same color (yellow). Then a fourth region, for which we needed a third color (red). And eventually other two regions, each of which touches all the previously used colors.
It is not difficult, playing a little with the maps, to realize that if the map has enough regions then we could be forced to use an arbitrarily large number of colors. Below you can see the construction of a map that needs 6 colors. While not minimal, it has the advantage tha it can be easily generalized to any number of colors.
Let's start with 16 disconnected regions, for which a single color suffices:
The new regions need a second color:
An a third one:
A fourth color is needed here:
A fifth one:
And the sixth color:
So, starting from 16 regions and adding other 8+4+2+1+1 = 16 regions, we build a map that needs 6 colors to be incrementally colored. The disconnection of the initial regions is not really needed:
It is interesting to note that the maps with this structure can be colored with just two colors:
Generalizing the example above (thus starting with 64, 128, 256,... orange regions to force 7, 8, 9,... colors), it is easy to show that for any number k it exists a map with 2^(k-1) regions that needs k colors.
Then next question, which I would like to see answered, is "which is the smallest number of regions to force the use of, say, k colors?". Indeed, it is easy to see that the construction above can be greatly improved and we do not need a map with 32 regions to force 6 colors.
So, how many regions do we need to force 6 or 7 colors? The answer is in the next page.