Michi’s blog » Blog Archive » On the chromatic number of Lichtenstein

On the chromatic number of Lichtenstein

October 28th, 2008

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.

6 People had this to say...

Michael Lugo Said...

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?

October 28th, 2008 at 19:50

Michi Said...

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

October 28th, 2008 at 20:54

Brian Hayes Said...

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.

October 28th, 2008 at 21:13

Michi Said...

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.

October 28th, 2008 at 21:20

D. Eppstein Said...

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.

October 28th, 2008 at 21:42

Carnival of Mathematics 47, where no, well… « JD2718 Said...

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

January 17th, 2009 at 21:56

Want your say?

post navigation

about: Michi is a recent PhD working in homological algebra and applied algebraic topology. This blog is his outlet for texts with some manner of thought put into them. Over at his LiveJournal intimate details and streams of consciousness might be found.
Not all here is mathematics. All here, though, are my personal thoughts and opinions. Please read the about page (linked above) for more details.
This blog uses statcounter.com for logging and traffic analysis. In order to identify return visitors, this site will issue a cookie on viewing the blog.

Travel plans