Michi's Blog

On the chromatic number of Lichtenstein

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 -- Vaduz2
  Gamprin1 -- Schaan1
  Gamprin1 -- Planken3
  Gamprin1 -- Eschen1
  Eschen1 -- Gamprin2
  Eschen1 -- Planken1
  Eschen2 -- Schaan1
  Vaduz3 -- Schaan1
  Vaduz2 -- Schaan1
  Planken3 -- Schaan1
  Planken2 -- Schaan1
  Schaan1 -- Planken1
  Schaan1 -- Planken4
  Schaan1 -- Vaduz1
  Gamprin2 -- Eschen3
  Eschen3 -- Vaduz4
  Eschen3 -- Schaan2
  Vaduz4 -- Schaan2
  Vaduz4 -- Planken1
  Schaan2 -- Planken1
  Planken1 -- Schaan3
  Vaduz1 -- Triesenberg1
  Vaduz1 -- Triesen
  Planken4 -- Triesenberg1
  Planken4 -- Balzers2
  Balzers2 -- Vaduz5
  Balzers2 -- Schaan4
  Vaduz5 -- Schaan4
  Schaan4 -- Triesenberg1
  Schaan4 -- Vaduz6
  Schaan4 -- Triesenberg2
  Triesenberg1 -- Vaduz6
  Triesenberg1 -- Triesen
  Triesenberg1 -- Balzers3
  Triesen -- Balzers3
  Triesen -- Balzers1
  Triesen -- Schaan5
  Vaduz6 -- 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
Vaduz: 7

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.

social