Monday, January 17, 2011

Coloring Maps

The four color theorem means you can color the United States in four colors. But can you color it in three? Try it before you read on.


The answer is no. Consider Nevada. It takes three colors to color that states that surround Nevada (Oregon, Idaho, Utah, Arizona and California) and then one more for Nevada.

I use this as an example of a heuristic in the P v NP book I'm working on. But what about the converse: Can a map have no internal states with an odd number of neighbors and still require four colors. I can come up with some examples but they all require either a lake separating states (like Lake Michigan) or more than three states coming together at a point (like the Four Corners of Utah, Arizona, New Mexico and Colorado).

I wrote this question in terms of planar graphs and asked it on Theory Q&A. Turns out there are no other examples. Take any map, where all internal states have an even number of neighbors with no lakes and no point that borders more than three states and that map can be three colored. Cool.

I'd like to find natural examples, real maps of anywhere where
1) At least two internal regions (to make it interesting)
2) All internal regions have an even number of neighbors
3a) The map is not three colorable (has lakes or more than three regions meeting in a point), or
3b) There are no lakes or more than three regions meeting in a point (so three colorable).

If you are the first to give me an example I use in the book, I'll send you a free copy of the book when it is published.


17 comments:

  1. The county map of Maine is relatively simple: no "four corners" places, and a single instance of an internal county with five neighbors: Androscoggin.

    ReplyDelete
  2. The map of Spanish states (http://www.ambientjobs.com/siteimages/map_spain.jpg)
    is three-colorable, and contains three interal regions.

    ReplyDelete
  3. The map of Spanish regions is interesting in that internal region Castile-La Mancha borders on seven other regions, but because Madrid breaks up the border between Castile-La Mancha and Castile-Leon, there are eight "neighbors."

    ReplyDelete
  4. The provinces of Armenia have two internal regions each with an even number of neighbors: http://upload.wikimedia.org/wikipedia/commons/thumb/7/71/Armenia_provinces_english.png/250px-Armenia_provinces_english.png

    ReplyDelete
  5. Your phrasing of the question in terms of planar graphs and your phrasing in terms of regions here don't quite match up to each other, because the dual of a set of regions might be a multigraph rather than a graph. Specifically, one way of getting a map requiring four regions is to start with a map in which one of the internal regions X has an odd number of neighbors, and then add a country with only two neighbors X and Y, partitioning the boundary of X and Y into two parts. Then X has an even number of neighboring regions even though the corresponding vertex in the dual multigraph has odd degree.

    Countries with only two neighbors include the US, Andorra, Moldova, and Mongolia but in all of these cases their neighbors aren't landlocked so nothing interesting happens. But this same principle allows Switzerland and the countries surrounding it to be three-colored even though Switzerland has five neighbors, and it causes Austria and the countries surrounding it to require four colors even though Austria has eight neighbors, because of Liechtenstein on the Swiss-Austrian border.

    ReplyDelete
  6. Uh, "requiring four regions" should have been "requiring four colors", obviously. And in the first sentence of my comment, I was intending to contrast the phrasing at cstheory vs the phrasing on this blog post.

    ReplyDelete
  7. Thanks for the examples and comments. I'm still looking for a real example for 3a.

    ReplyDelete
  8. For an example of 3a: If I'm not mistaken, the regions of Estonia? http://www.geni.org/globalenergy/library/national_energy_grid/estonia/graphics/ee-div.gif Järvamaa and Raplamaa being the internal regions.

    ReplyDelete
  9. Estonia is another example of 3b and it can be three colored.

    ReplyDelete
  10. I think this is an example of 3a, with lakes:

    In the following list of states and provinces, if they were to be three-colorable, the capitalized ones would all have to be the same color because each two consecutive capitalized ones borders both of the lower case ones between them. But the first and last are adjacent, so four colors are needed:

    MICHIGAN, ohio, indiana, KENTUCKY, illinois, missouri, IOWA, south dakota, minnesota, NORTH DAKOTA, minnesota (again), manitoba, ONTARIO.

    None of these is entirely surrounded by the others even if you also include Wisconsin — many of them are on the Great Lakes and the rest of them are all on the outside boundary of the overall region. Also the inability to three-color these regions doesn't involve the disconnectedness of Michigan — it doesn't help to color the parts two different colors — because the argument above only used the adjacencies of Lower Michigan.

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

    ReplyDelete
  12. Sorry for the wrong map of Butler (there's a region with 7 neighbors). If historic region counts, the map of the former Tripolitania (as a province of Libra) in 1988 seems to be a candidate: three internal regions all with even number of neighbors, and a quadripoint. The wiki article contains more information.

    ReplyDelete
  13. This map of southwest Asia, if you ignore Armenia, Azerbaijan and Georgia (due to that exclave). If you don't mind an exclave as a non-separate region , then you can include this (but on its own has 3 neighbors).

    http://www.mytravelguide.com/g/maps/Southwest-Asia-map.gif

    Internal Regions:

    Afghanistan with 6 neighboors, Tajikistan with 4, Kyrgyzstan with 4, Nepal with 2 and Bhutan with 2.

    The map is not 3-colorable, since there is a corner for Afghanistan-Pakistan-Iran and also the Wakhan Corridor. http://en.wikipedia.org/wiki/Wakhan_Corridor

    Note that Iraq is not an internal region and that Bangladesh and Nepal do not share any border, at least according to Wikipedia.

    I also like this map because although I am not very familiar with the region's history, you can tell there has been a lot of turmoil just from the irregular shapes and structure you do not fight in other maps.

    ReplyDelete
  14. Check out the districts of Cyprus. http://www.geographicguide.com/europe-maps/cyprus.htm

    If we consider the U.N. buffer zone as it's own separate area, then the U.N. buffer zone, Nicosia, Famagusta, and Larnaca form K4.

    ReplyDelete
  15. Map of South-Western Administrative Okrug of Moscow:

    http://en.wikipedia.org/wiki/File:Msk_uzao.png

    fulfills your requirements 1,2,3a.

    The map of Northern Administrative Okrug of Moscow:

    http://en.wikipedia.org/wiki/File:Msk_sao.png

    fulfills requirements 1,2, and has points in which 4 areas meet, but it is 3-colourable

    The map of Western and Northwestern Okrugs of Moscow together fulfills 1,2, 3b

    ReplyDelete
  16. Another example for 1,2,3a, city of Mainz:

    http://upload.wikimedia.org/wikipedia/commons/7/71/Mainz_gesamt.svg

    ReplyDelete
  17. Mainz is so close but it is 3-colorable. If only Alt-stadt and Weisenau shared a border. http://upload.wikimedia.org/wikipedia/commons/7/78/Mainz_subdivisions.svg

    ReplyDelete