tag:blogger.com,1999:blog-3722233.post8666700975500965537..comments2024-03-28T18:17:00.135-05:00Comments on Computational Complexity: Coloring MapsLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger17125tag:blogger.com,1999:blog-3722233.post-19731289360522793312011-07-07T11:02:26.140-05:002011-07-07T11:02:26.140-05:00Mainz is so close but it is 3-colorable. If only A...Mainz is so close but it is 3-colorable. If only Alt-stadt and Weisenau shared a border. <a href="http://upload.wikimedia.org/wikipedia/commons/7/78/Mainz_subdivisions.svg" rel="nofollow">http://upload.wikimedia.org/wikipedia/commons/7/78/Mainz_subdivisions.svg</a>Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-4249700066993593862011-03-27T17:08:43.939-05:002011-03-27T17:08:43.939-05:00Another example for 1,2,3a, city of Mainz:
http:/...Another example for 1,2,3a, city of Mainz:<br /><br />http://upload.wikimedia.org/wikipedia/commons/7/71/Mainz_gesamt.svgLukasz Grabowskihttps://www.blogger.com/profile/12330558387447969321noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-15735769873701155952011-03-27T09:43:14.218-05:002011-03-27T09:43:14.218-05:00Map of South-Western Administrative Okrug of Mosco...Map of South-Western Administrative Okrug of Moscow:<br /><br />http://en.wikipedia.org/wiki/File:Msk_uzao.png<br /><br />fulfills your requirements 1,2,3a.<br /><br />The map of Northern Administrative Okrug of Moscow:<br /><br />http://en.wikipedia.org/wiki/File:Msk_sao.png<br /><br />fulfills requirements 1,2, and has points in which 4 areas meet, but it is 3-colourable<br /><br />The map of Western and Northwestern Okrugs of Moscow together fulfills 1,2, 3bLukasz Grabowskihttps://www.blogger.com/profile/12330558387447969321noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-46233605145651883402011-01-19T17:08:14.542-06:002011-01-19T17:08:14.542-06:00Check out the districts of Cyprus. http://www.geog...Check out the districts of Cyprus. http://www.geographicguide.com/europe-maps/cyprus.htm<br /><br />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.beero1000https://www.blogger.com/profile/01071276341056185027noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-46013561266107328252011-01-19T14:08:35.672-06:002011-01-19T14:08:35.672-06:00This map of southwest Asia, if you ignore Armenia,...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).<br /><br />http://www.mytravelguide.com/g/maps/Southwest-Asia-map.gif<br /><br />Internal Regions: <br /><br />Afghanistan with 6 neighboors, Tajikistan with 4, Kyrgyzstan with 4, Nepal with 2 and Bhutan with 2.<br /><br />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<br /><br />Note that Iraq is not an internal region and that Bangladesh and Nepal do not share any border, at least according to Wikipedia.<br /><br />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.Anonymoushttps://www.blogger.com/profile/09364120444779754928noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-87002198516318822332011-01-19T09:05:27.993-06:002011-01-19T09:05:27.993-06:00Sorry for the wrong map of Butler (there's a r...Sorry for the wrong map of Butler (there's a region with 7 neighbors). If historic region counts, the <a href="http://en.wikipedia.org/wiki/File:Libia_regions_with_numbers.svg" rel="nofollow">map</a> of the former <a href="http://en.wikipedia.org/wiki/Tripolitania" rel="nofollow">Tripolitania</a> (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 <a href="http://en.wikipedia.org/wiki/Districts_of_Libya" rel="nofollow">wiki article</a> contains more information.Hsien-Chih Changhttps://www.blogger.com/profile/06366019701570525288noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-13933719965181515112011-01-19T00:58:35.940-06:002011-01-19T00:58:35.940-06:00This comment has been removed by the author.Hsien-Chih Changhttps://www.blogger.com/profile/06366019701570525288noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-39998763165179444652011-01-18T23:21:09.171-06:002011-01-18T23:21:09.171-06:00I think this is an example of 3a, with lakes:
In ...I think this is an example of 3a, with lakes:<br /><br />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:<br /><br />MICHIGAN, ohio, indiana, KENTUCKY, illinois, missouri, IOWA, south dakota, minnesota, NORTH DAKOTA, minnesota (again), manitoba, ONTARIO.<br /><br />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.David Eppsteinhttp://11011110.livejournal.com/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-23231816080687330342011-01-18T10:29:58.484-06:002011-01-18T10:29:58.484-06:00Estonia is another example of 3b and it can be thr...Estonia is another example of 3b and it can be three colored.Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-67175110297034799362011-01-18T09:57:42.912-06:002011-01-18T09:57:42.912-06:00For an example of 3a: If I'm not mistaken, the...For an example of 3a: If I'm not mistaken, the regions of Estonia? <a rel="nofollow">http://www.geni.org/globalenergy/library/national_energy_grid/estonia/graphics/ee-div.gif</a> Järvamaa and Raplamaa being the internal regions.Unknownhttps://www.blogger.com/profile/15392080295805347772noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-61343981106264826782011-01-18T09:24:12.236-06:002011-01-18T09:24:12.236-06:00Thanks for the examples and comments. I'm stil...Thanks for the examples and comments. I'm still looking for a real example for 3a.Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-75854887908788999512011-01-17T19:38:36.115-06:002011-01-17T19:38:36.115-06:00Uh, "requiring four regions" should have...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.David Eppsteinhttp://11011110.livejournal.com/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-68969483842616234352011-01-17T19:24:07.891-06:002011-01-17T19:24:07.891-06:00Your phrasing of the question in terms of planar g...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.<br /><br />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.David Eppsteinhttp://11011110.livejournal.com/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-7264414703713725102011-01-17T11:40:59.372-06:002011-01-17T11:40:59.372-06:00The provinces of Armenia have two internal regions...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.pngChris Bogarthttps://www.blogger.com/profile/08163342331118448067noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-72174695519261981202011-01-17T11:30:11.451-06:002011-01-17T11:30:11.451-06:00The map of Spanish regions is interesting in that ...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."Eriknoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-69053435591652213752011-01-17T10:55:53.094-06:002011-01-17T10:55:53.094-06:00The map of Spanish states (http://www.ambientjobs....The map of Spanish states (http://www.ambientjobs.com/siteimages/map_spain.jpg)<br />is three-colorable, and contains three interal regions.Charles Martelnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-56314266810318216612011-01-17T10:44:14.571-06:002011-01-17T10:44:14.571-06:00The county map of Maine is relatively simple: no &...The <a href="http://en.wikipedia.org/wiki/File:Maine-counties-map.gif" rel="nofollow">county map of Maine</a> is relatively simple: no "four corners" places, and a single instance of an internal county with five neighbors: Androscoggin.Derrick Stoleehttps://www.blogger.com/profile/08788683962503964865noreply@blogger.com