But I also wanted a natural example that was four-colorable even though every interior region had an even number of neighbors. In my book I ended up making up my own fake country map.
(Sorry for the hand-drawn picture and getting East-West wrong. Looks better in the book)
So once again I'd still like to see a natural example. Here's a simple 7-node graph with every interior node with even degree but not 3-colorable.
There must be some real world map that captures this graph.
I'll make the same deal I made before, an autographed copy of my book for the best example of a real-world example of a non-three colorable map with interior regions with an even number of neighbors. Should be a real political unit--not just a collection of states.
Lorri and Shirak are adjacent and have the same color in your example.
ReplyDeleteShirak should have been blue in the picture.
DeleteYou can use the following image instead: http://imgur.com/9JyRBxE
DeleteA map of Canada (which showed the US as one country) would do!
ReplyDeleteThe United States (with the whole of the US colored a single color) is the exterior node of degree 4.
The row of 4 is Alberta, Saskatchewan, Manitoba, Ontario.
The row of 2 is the Northwest Territories and Nunavut.
The key insight was that the "interior square" required four regions to meet at a corner, which meant that it had to be a quadripoint, which greatly narrowed the search.
This is slightly cheating, as Nunavut and Ontario do not actually touch. However, they are at times separated by only 10 miles of Hudson Bay (at Akimiski Island) and so they should not be given the same color.
Poland at the top; Germany, Czech Republic, Slovakia, Ukraine in the middle; Austria, Hungary at the lower level: http://www.youreuropemap.com/europe_map_political.gif
ReplyDeleteSlovakia has five neighbors.
DeleteAs I said on Twitter, the Amsterdam map of the 7 (or 8 if add Zuidoost) 'Stadsdelen'. Can be found here. http://www.amsterdam.nl/gemeente/stadsdelen/ (note that several Stasdelen have merged in 2010, creating the 7 (or 8) remaining units)
ReplyDeleteAlas the West has five neighbors.
DeleteIsn't there a graph of the countries in the world and their internal divisions where we can use an algorithm to search?
ReplyDeleteLooking at the previous comments, I think you should point out that triangulated maps have no chance to work and repeat once more that you want every interior country to have an even number of neighbors.
ReplyDeleteThis comment has been removed by the author.
ReplyDeleteSo, here is a nice example if two states meeting in point can share the same color:
ReplyDeletehttp://www.mapsofindia.com/maps/india/india-political-map.htm
On this map, consider Uttar Pradesh and the states (+Nepal) around it. (Note that Haryana, HP, Uttarakhand and UP all meet in one point, so in our graph HP and UP are not connected.) Of course we have to restrict the map to the north, otherwise other states would ruin it.
Also, the reason why this works is that UP is practically surrounded by an odd cycle, since Punjab and Rajasthan force HP to have a different color from its neighbors. I think a similar trick is used in your 7-node graph.
If you prefer regions sharing one point to be adjacent, consider Zambia and its neighbors (including Botswana) plus Ruanda:
http://4.bp.blogspot.com/-KdIYsrIb3JI/T8GrXoBmx5I/AAAAAAAACKE/kF8wqy1f6dI/s1600/Africa-Political-Region-Map.gif
Again, make sure not to include South Africa, or suppose that Namibia does not neighbor Zimbabwe.
Seems like the south of Africa construction is not good, I have not noticed that there was Malawi making a K_4...
DeletePity, because Zambia neighbors Botswana and Namibia does not Zimbabwe according to wiki:
http://en.wikipedia.org/wiki/Kazungula,_Zambia
I have the perfect example! Take the political map of the Balkan before 1989, so the countries are Turkey, Greece, Bulgaria, Albania, Yugoslavia, Hungary, Romania and the Soviet Union. (Optionally add Czechoslovakia, Poland and East Germany.) This you cannot 3 color because Bulgaria practically has a cycle of length 5 around it (Hungary forces SU to differ from Bulgaria's color).
ReplyDeleteHm, I just realized that my example has your graph as an induced subgraph! Yugoslavia plays the role of your top degree four vertex.
DeleteHate to seem over-confident and demanding but where is my book?
DeleteA link to the map: http://www.euratlas.net/history/hisatlas/europe/198922EP.jpg
DeleteOK Dom. Email me your address and I'll send you a book.
DeleteThe administrative map of Bangladesh. Because of the Jhalkathi district you need at list four colors. Here is the map. http://en.wikipedia.org/wiki/File:Bangladesh_Jhalokati_District.png .
ReplyDelete- Shehab
This map has a region with an odd number of neighbors.
Delete