Michi’s blog » On the chromatic number of Lichtenstein

## On the chromatic number of Lichtenstein

• October 28th, 2008
• 7:41 pm

Following the featuring of the internal political structure of Lichtenstein on the Strange Maps blog, Brian Hayes asks for the chromatic number of Lichtenstein.

Rahul pointed out that I made errors in transferring the map to a graph. Specifically, I missed the borders Schellenberg-Eschen and Vaduz-Triesen. The post below changes accordingly.

Warning: This post DOES contain spoilers to Brian’s question. If you do want to investigate it yourself, you’ll need to stop reading now. Apologies to those on my planet feeds.

As a first step, we need to build a graph out of it. I labeled each region in turn with the exclaves numbered higher than the “main” region of each organizational unit. And then I build a .dot file to capture them all:

graph Lichtenstein {
Ruggell -- Schellenberg
Ruggell -- Gamprin1
Schellenberg -- Mauren
Schellenberg -- Eschen1
Mauren -- Eschen1
Gamprin1 -- Eschen2
Gamprin1 -- Schaan1
Gamprin1 -- Planken3
Gamprin1 -- Eschen1
Eschen1 -- Gamprin2
Eschen1 -- Planken1
Eschen2 -- Schaan1
Planken3 -- Schaan1
Planken2 -- Schaan1
Schaan1 -- Planken1
Schaan1 -- Planken4
Gamprin2 -- Eschen3
Eschen3 -- Schaan2
Schaan2 -- Planken1
Planken1 -- Schaan3
Planken4 -- Triesenberg1
Planken4 -- Balzers2
Balzers2 -- Schaan4
Schaan4 -- Triesenberg1
Schaan4 -- Triesenberg2
Triesenberg1 -- Triesen
Triesenberg1 -- Balzers3
Triesen -- Balzers3
Triesen -- Balzers1
Triesen -- Schaan5
Triesenberg2 -- Schaan5
}


Compiling this, we get the graph

Now, with this it is an easy job to get the adjacency graph for the communes. We can just delete all numbers in the above dot file. Graphing that, we get instead

Note, however, that the massive duplication of adjacency edges makes this rather hard to read. So we can just amalgamate all those edges into one single edge each. So in the end, the Liechtenstein graph turns out to be

Now, as Brian points out, there is a 5-clique in this map, given by Schaan, Balzers, Vaduz, Planken, Triesenberg.

Edited: Michael Lugo pointed out in the comments that my exclusion criterion for 6-cliques is obviously and trivially false. Discussion below here changed appropriately

If there were a 6-clique in the map, there would have to be 6 communes each of which have at least 5 edges connected to them. We can construct the table of degrees for all communes, to see whether this helps:
Balzers: 5
Eschen: 6
Gamprin: 5
Mauren: 2
Planken: 6
Ruggell: 2
Schaan: 7
Schellenberg: 3
Triesen: 4
Triesenberg: 5

So, we have enough edges in Balzers, Eschen, Gamprin, Planken, Schaan, Triesenberg and Vaduz. This gives us 7 candidates for a 6-clique. Thus if two of these have too many edges outside this group, we know that there cannot be a 6-clique in the commune-graph.

Now note that Triesenberg borders to Triesen, so at most 4 of those 5 edges can be within a 6-clique. Also, Gamprin borders to Ruggell, so at most 4 of Gamprin’s 5 edges can be within a 6-clique. Thus the graph contains no 6-cliques.

Does this, though, mean that we can construct a 5-coloring of the graph? Try this on:

I would recolor the Liechtenstein map using this color choice, but I haven’t gotten around to installing a decent picture editing program just yet. That’ll have to wait.

### 6 People had this to say...

To have a 6-clique, you’d need 6 nodes each with at least 5 edges, right? (That is, each node would have to connect to each of the other nodes in the clique.) Or am I missing something?

• Michi
• October 28th, 2008
• 20:54

Michael: Quite correct. I’ve changed the post to reflect this. Thank you.

Very nicely done. Thank you.

I’m curious what program you used to render the .dot file, and did it produce that output directly, or did you manually rearrange the nodes to approximate the actual geography?

I would recolor the Liechtenstein map using this color choice, but I haven’t gotten around to installing a decent picture editing program just yet. That’ll have to wait.

If you do so, the result will be quite unintelligible. There will be no adjacent regions that share a color, but there will be no way of guessing which like-colored regions are actually parts of the same commune.

• Michi
• October 28th, 2008
• 21:20

Welcome here, Brian.

I hope you got to see the debugged version of it all – Michael and Rahul pointed out quite critical bugs in it.

I used Graphviz on MacOSX to render the graphs – and the algorithm occasionally mirrors the geography, but much of it follows from the spring dynamics engine. I didn’t rearrange anything.

I am aware that the recolored map will be unintelligible – which was part of my point of wanting to draw it that way: show exactly how bad a decision that would have been.

I think for this sort of map visualization problem, coloring with a minimal number of colors is not the right thing to do. Because, if you color e.g. Ruggel and Mauren the same color, how can you tell when you look at the map whether they are two different cantons or two disconnected pieces of the same canton?

In arxiv:cs.CG/0609033 I and my co-authors looked at a similar problem of choosing colors to visualize a partition of the plane into regions that might be disconnected. The point of view we ended up taking was that each region should have its own color, that these colors should all be chosen as visually distinct as possible, and that colors of neighboring pairs of cantons should be chosen to have especially strong contrast in order to make the borders stand out. We then modeled this as a problem of embedding the adjacency graph of the map into three-dimensional color space. Here’s a blog post with the resulting visualization.

[...] on the Chromatic Number of Lichtenstein. John Kemeny has photos of mathematicians … and more of the same … but is looking for [...]