My Constraint Programming Blog

In The Chromatic Number of Liechtenstein bit-player asked (2008-10-28)) the following about coloring the map of Lichtenstein:

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.

...

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?

I wrote a MiniZinc model for this minimizing problem: lichtenstein_coloring.mzn.

The model has two variable arrays:
* color_communes: the color of the 11 communes
* color: the color of the 29 en-/exclaves

Objective: minimize the number of colors used.

The Gecode/flatzinc solver gives the following solutions in less than 1 second, which states that 5 different colors (n_colors) is sufficient. The model allows for up to 11 different colors, hence the large color numbers.

n_colors: 5
color_communes: [1, 1, 10, 8, 8, 1, 9, 9, 8, 10, 11]
color: [1, 1, 1, 1, 1, 1, 10, 10, 8, 8, 8, 8, 8, 1, 9, 9, 9, 9, 9, 9, 8, 10, 10, 11, 11, 11, 11, 11, 11]

Times for other MiniZinc solvers:
* Minizinc's flatzinc: 2 seconds,
* Minizinc's fdmip: 2 seconds,
* ECLiPSe's ic: 4 seconds
* tinifz: 5.5 seconds

Also see
The chromatic number of Lichtenstein by Michi (from whom I borrowed the edges).