Thursday, May 02, 2013

Map Coloring Revisited

Following the coloring theme from Bill's last post, a few years ago I asked you readers for natural examples of maps that were and were not three colorable. Chris Bogart gave a nice non-trivial example of a three-colorable country, Armenia.




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. 

20 comments:

  1. Lorri and Shirak are adjacent and have the same color in your example.

    ReplyDelete
    Replies
    1. Shirak should have been blue in the picture.

      Delete
    2. You can use the following image instead: http://imgur.com/9JyRBxE

      Delete
  2. A map of Canada (which showed the US as one country) would do!

    The 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.

    ReplyDelete
  3. 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

    ReplyDelete
  4. As 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)

    ReplyDelete
  5. Isn't there a graph of the countries in the world and their internal divisions where we can use an algorithm to search?

    ReplyDelete
  6. Looking 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.

    ReplyDelete
  7. This comment has been removed by the author.

    ReplyDelete
  8. So, here is a nice example if two states meeting in point can share the same color:
    http://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.

    ReplyDelete
    Replies
    1. Seems like the south of Africa construction is not good, I have not noticed that there was Malawi making a K_4...
      Pity, because Zambia neighbors Botswana and Namibia does not Zimbabwe according to wiki:
      http://en.wikipedia.org/wiki/Kazungula,_Zambia

      Delete
  9. 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).

    ReplyDelete
    Replies
    1. Hm, I just realized that my example has your graph as an induced subgraph! Yugoslavia plays the role of your top degree four vertex.

      Delete
    2. Hate to seem over-confident and demanding but where is my book?

      Delete
    3. A link to the map: http://www.euratlas.net/history/hisatlas/europe/198922EP.jpg

      Delete
    4. OK Dom. Email me your address and I'll send you a book.

      Delete
  10. The 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 .

    - Shehab

    ReplyDelete
    Replies
    1. This map has a region with an odd number of neighbors.

      Delete