Skip to Content »

Michi’s blog » More on Lichtenstein

More on Lichtenstein

  • October 28th, 2008
  • 11:03 pm

It turns out that there is even more to say on the communes of Lichtenstein.

First of all, there is a 5-clique in the communal graph, as Brian Hayes pointed out. But there are two different excluded subgraphs for planarity – so if we aren’t looking specifically for the chromatic number, but rather how this graph fails to be a “normal” land map, we might want to see whether it realizes BOTH.

It turns out that it does.

The following are two highlighted versions of the Liechtenstein communal graph.


The embedded K5 with edges in blue.


The embedded K33 with blue and red vertices.

2 People had this to say...

Gravatar
  • Cahit
  • October 30th, 2008
  • 7:16

I reached to the same conclusion without searching the clique of size 5 and K_3,3. Uses only spiral chain coloring algorithm on the map and uses the same color for the common communes.

See:

http://www.flickr.com/photos/49058045@N00/2985004680/

Cahit

Gravatar
  • Michi
  • October 30th, 2008
  • 8:11

Do note that my searching for K5 and K33 was not motivated by trying to find the chromatic number. That I dealt with in the previous blogpost. This post was more a question of whether both the excluding graphs for planarity are realized in the Liechtenstein graph.

Nevertheless, I’m glad to see you reach the same conclusion, and I like your map.

Want your say?

* Required fields. Your e-mail address will not be published on this site

You can use the following XHTML tags:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>