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.
The county map of Maine is relatively simple: no "four corners" places, and a single instance of an internal county with five neighbors: Androscoggin.
ReplyDeleteThe map of Spanish states (http://www.ambientjobs.com/siteimages/map_spain.jpg)
ReplyDeleteis three-colorable, and contains three interal regions.
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."
ReplyDeleteThe 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
ReplyDeleteYour 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.
ReplyDeleteCountries 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.
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.
ReplyDeleteThanks for the examples and comments. I'm still looking for a real example for 3a.
ReplyDeleteFor 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.
ReplyDeleteEstonia is another example of 3b and it can be three colored.
ReplyDeleteI think this is an example of 3a, with lakes:
ReplyDeleteIn 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.
This comment has been removed by the author.
ReplyDeleteSorry 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.
ReplyDeleteThis 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).
ReplyDeletehttp://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.
Check out the districts of Cyprus. http://www.geographicguide.com/europe-maps/cyprus.htm
ReplyDeleteIf 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.
Map of South-Western Administrative Okrug of Moscow:
ReplyDeletehttp://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
Another example for 1,2,3a, city of Mainz:
ReplyDeletehttp://upload.wikimedia.org/wikipedia/commons/7/71/Mainz_gesamt.svg
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