# 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 }

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

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.

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.