tag:blogger.com,1999:blog-3722233.post6104783592773884772..comments2024-03-28T18:17:00.135-05:00Comments on Computational Complexity: Map Coloring RevisitedLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger20125tag:blogger.com,1999:blog-3722233.post-33859840648422156832013-07-22T22:24:51.431-05:002013-07-22T22:24:51.431-05:00OK Dom. Email me your address and I'll send yo...OK Dom. Email me your address and I'll send you a book.Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-59332808385636427162013-07-22T15:00:34.721-05:002013-07-22T15:00:34.721-05:00A link to the map: http://www.euratlas.net/history...A link to the map: http://www.euratlas.net/history/hisatlas/europe/198922EP.jpgdomhttps://www.blogger.com/profile/05790539025733385232noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-27495090101982666862013-07-22T10:15:51.526-05:002013-07-22T10:15:51.526-05:00This map has a region with an odd number of neighb...This map has a region with an odd number of neighbors.Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-53586162642238388092013-07-21T12:21:32.522-05:002013-07-21T12:21:32.522-05:00Hate to seem over-confident and demanding but wher...Hate to seem over-confident and demanding but where is my book?domhttps://www.blogger.com/profile/05790539025733385232noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-16970643495891427462013-05-13T07:34:21.437-05:002013-05-13T07:34:21.437-05:00Hm, I just realized that my example has your graph...Hm, I just realized that my example has your graph as an induced subgraph! Yugoslavia plays the role of your top degree four vertex.domhttps://www.blogger.com/profile/05790539025733385232noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-35842495406606788632013-05-08T16:10:30.897-05:002013-05-08T16:10:30.897-05:00The administrative map of Bangladesh. Because of t...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 . <br /><br />- Shehab<br />Shehabhttps://www.blogger.com/profile/14005206657539890819noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-87934515794327454112013-05-06T01:23:56.703-05:002013-05-06T01:23:56.703-05:00I have the perfect example! Take the political map...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).domhttps://www.blogger.com/profile/05790539025733385232noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-41405460111073243432013-05-05T10:10:27.634-05:002013-05-05T10:10:27.634-05:00Seems like the south of Africa construction is not...Seems like the south of Africa construction is not good, I have not noticed that there was Malawi making a K_4...<br />Pity, because Zambia neighbors Botswana and Namibia does not Zimbabwe according to wiki:<br />http://en.wikipedia.org/wiki/Kazungula,_Zambiadomhttps://www.blogger.com/profile/05790539025733385232noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-81879200114329184512013-05-03T23:51:39.708-05:002013-05-03T23:51:39.708-05:00So, here is a nice example if two states meeting i...So, here is a nice example if two states meeting in point can share the same color:<br />http://www.mapsofindia.com/maps/india/india-political-map.htm<br />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.<br /><br />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. <br /><br />If you prefer regions sharing one point to be adjacent, consider Zambia and its neighbors (including Botswana) plus Ruanda:<br />http://4.bp.blogspot.com/-KdIYsrIb3JI/T8GrXoBmx5I/AAAAAAAACKE/kF8wqy1f6dI/s1600/Africa-Political-Region-Map.gif<br />Again, make sure not to include South Africa, or suppose that Namibia does not neighbor Zimbabwe.domhttps://www.blogger.com/profile/05790539025733385232noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-19979257146234609722013-05-03T13:34:16.070-05:002013-05-03T13:34:16.070-05:00You can use the following image instead: http://i...You can use the following image instead: http://imgur.com/9JyRBxE Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-56368597059976195762013-05-03T10:43:12.516-05:002013-05-03T10:43:12.516-05:00This comment has been removed by the author.domhttps://www.blogger.com/profile/05790539025733385232noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-59969643719405355432013-05-03T03:40:03.478-05:002013-05-03T03:40:03.478-05:00Looking at the previous comments, I think you shou...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.domhttps://www.blogger.com/profile/05790539025733385232noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-42971180497379585572013-05-03T03:35:16.789-05:002013-05-03T03:35:16.789-05:00Slovakia has five neighbors.Slovakia has five neighbors.domhttps://www.blogger.com/profile/05790539025733385232noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-77673089026750060872013-05-02T19:12:30.324-05:002013-05-02T19:12:30.324-05:00Isn't there a graph of the countries in the wo...Isn't there a graph of the countries in the world and their internal divisions where we can use an algorithm to search? Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-66655640856863333262013-05-02T14:08:55.434-05:002013-05-02T14:08:55.434-05:00Alas the West has five neighbors.Alas the West has five neighbors.Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-12134672919097442542013-05-02T14:07:20.064-05:002013-05-02T14:07:20.064-05:00Shirak should have been blue in the picture.Shirak should have been blue in the picture.Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-45994119360695399222013-05-02T08:59:09.434-05:002013-05-02T08:59:09.434-05:00As I said on Twitter, the Amsterdam map of the 7 (...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) Franknoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-41542196398423804522013-05-02T08:39:24.490-05:002013-05-02T08:39:24.490-05:00Poland at the top; Germany, Czech Republic, Slovak...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.gifKostas Bekrishttps://www.blogger.com/profile/00635996893346658951noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-36799501180214652132013-05-02T08:23:27.224-05:002013-05-02T08:23:27.224-05:00A map of Canada (which showed the US as one countr...A map of Canada (which showed the US as one country) would do!<br /><br />The United States (with the whole of the US colored a single color) is the exterior node of degree 4.<br /><br />The row of 4 is Alberta, Saskatchewan, Manitoba, Ontario.<br /><br />The row of 2 is the Northwest Territories and Nunavut.<br /><br />The key insight was that the "interior square" required four regions to meet at a corner, which meant that it had to be a <a href="http://en.wikipedia.org/wiki/Quadripoint" rel="nofollow">quadripoint</a>, which greatly narrowed the search.<br /><br />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.Peterhttps://www.blogger.com/profile/17965824121030784289noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-86647976141829052202013-05-02T08:21:46.177-05:002013-05-02T08:21:46.177-05:00Lorri and Shirak are adjacent and have the same co...Lorri and Shirak are adjacent and have the same color in your example.Anonymousnoreply@blogger.com