Four colors suffice for any planar map: We’ve known that since 1977. If a map is divided into countries or provinces or other regions, and you want to color the map so that no two adjacent regions have the same color, you’ll never need more than four crayons. But there are a couple of definitions that have to be accepted if this theorem is to hold. First, “adjacent” means that two regions share a boundary segment, not merely a point or a discontinuous set of points. Second, a “region” has to be a connected area, so that you can reach any point in the interior from any other such point without crossing a boundary.
A few days ago the strange and wonderful Strange Maps blog called attention to this map of the Principality of Liechtenstein:
(The map comes from the Wikimedia Commons Atlas of Liechtenstein, which has a larger image.)
It seems that Liechtenstein is divided into 11 communes, which emphatically do not satisfy the connectivity requirement of the four color map theorem. Just four of the communes consist of a single connected area (Ruggell, Schellenberg and Mauren in the north, and Triesen in the south). All the rest of the communes have enclaves and/or exclaves. (I confess that I didn’t know the distinction between these words until yesterday. They make a nice pair.) The most fragmented commune is Vaduz, which includes the principality’s capital. Vaduz consists of six isolated pieces; the smallest is a sliver about a kilometer northeast of the town of Planken.
In the map above, each commune is assigned its own color, and so we have an 11-coloring. It’s easy to see we could make do with fewer colors, but how many fewer? I have found a five-clique within the map; that is, there are five communes that all share a segment of border with one another. It follows that a four-coloring is impossible. Is there a five-coloring? What is the chromatic number of Liechtenstein?
There is a five-coloring. See my blog.
I’m trying not to spoil too much in here.
There’s still more at Michi’s Blog. In addition, Ibrahim Cahit has produced an explicit five-coloring of the map itself, complete with Blackletter labels.
The map coloring problem given by the chromatic number of Liechtenstein is quite interesting from the point of graph coloring. You may deal with the constraint planar graph coloring problem if you only consider dual-graph of the map. Here constraint comes from the coloring of the nodes of the disjoint regions corresponding to the same commune with the same color. Equivalently you can study coloring of the map by coloring the nodes of the non-planar graph obtained by shrinking all regions of a commune to a single node (see Michi’s Blog). Then the coloring problem can be handled by the Hadwiger’s conjecture which says “every K_k-minor free graph is colorable with k-1 colors. I also note that one can design map of this kind for which the size of the maximum clique corresponding to the non-planar graph is equals to the number of communes.
What is the status on Hadwiger’s conjecture?
The Hadwiger’s conjecture which asserts that every loopless graph not contractible to the complete graph on k + 1 vertices is k-colorable. When k = 3 this is easy, and when k= 4, Wagner’s theorem of 1937 shows the conjecture to be equivalent to the four-color theorem (the 4CT)[1]. The case k = 5 it is also equivalent to the 4CT. Without assuming the 4CT, Robertson, Seymour and Thomas have shown that every minimal counterexample to Hadwiger’s conjecture, when k = 5 is apex ; that is, it consists of a planar graph with one additional vertex violating the planarity. Consequently, the 4CT implies Hadwiger’s conjecture when k = 5, because it implies that apex graphs are 5-colorable [2]. For other values of k the Hadwiger conjecture is open. Therefore the general graph coloring problem related with the Liechtenstein map is rely on the solution of the Hadwiger’s conjecture. But here we have the option to consider equivalently, coloring of the dual planar graph.
[1] K. Wagner, Uber eine Eigenschaft der ebenen Komplexe”, Math. Ann. 114 (1937),570-590.
[2] N. Robertson, P. Seymour, R. Thomas, Hadwiger’s conjecture for K6-free graphs, Combinatorica 14 (1993), 279-361.