tag:blogger.com,1999:blog-3722233.post114666374334039003..comments2020-10-27T10:22:30.630-05:00Comments on Computational Complexity: Four Coloring the United StatesLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger19125tag:blogger.com,1999:blog-3722233.post-1147631047895102592006-05-14T13:24:00.000-05:002006-05-14T13:24:00.000-05:001) http://images.google.ca/2) "four-color theorem"...1) http://images.google.ca/<BR/>2) "four-color theorem"<BR/>3) Hit Return<BR/>4) ???<BR/>5) PrOfIT!1!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1147174646191605952006-05-09T06:37:00.000-05:002006-05-09T06:37:00.000-05:00You can find four coloring of several maps based o...You can find four coloring of several maps based on "spiral chains" including the ones for the USA map at <BR/><BR/>http://www.flickr.com/photos/49058045@N00/<BR/><BR/>CahitAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1146879828379584322006-05-05T20:43:00.000-05:002006-05-05T20:43:00.000-05:00There seems to be a curious degrees of freedom iss...There seems to be a curious degrees of freedom issue with different ways of coloring the USA map. The Getech web site allows the following pairs of states to interchange colors: Arizona/Utah, Washington/Oregon, South Dakota/Nebraska, Florida/Alabama, Vermont/New Hampshire or New Hampshire/Maine. But your map seems to only have New Hampshire/Maine as states that can be interchanged in their colors. What do you make of this? Am I just over looking possibilities? Do other USA four colored maps have other degrees of freedom?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1146741625872423362006-05-04T06:20:00.000-05:002006-05-04T06:20:00.000-05:00Actually, the 4-color theorem does not quite direc...Actually, the 4-color theorem does not quite directly imply a 4-coloring of the 50 states because of the four corners.<BR/><BR/>On the other hand, the 50 states can be colored by the elementary result that a minimal graph that is not n-colorable has no vertex of degree less than n. The greedy algorithm works just fine, provided that the vertices are ordered in reverse according to their remaining valence.Greg Kuperberghttps://www.blogger.com/profile/03777237240198671451noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1146716359730880092006-05-03T23:19:00.000-05:002006-05-03T23:19:00.000-05:00Wikipedia's four colors are much nicer. Yours look...Wikipedia's four colors are much nicer. Yours look like screen scrape from an old IBM PC in CMY color mode. :-)<BR/><BR/>Also, 4-colorability of a planar graph is in P and even in L and smaller complexity classes. :-) It is on a par with the sometimes-stated problem of factoring a prime number.<BR/><BR/>On the other hand, 4-coloring a planar graph is interesting and it's a neat result that it is O(n^2).Greg Kuperberghttps://www.blogger.com/profile/03777237240198671451noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1146707703136977272006-05-03T20:55:00.000-05:002006-05-03T20:55:00.000-05:00So, uh, which ones voted for Kerry again?So, uh, which ones voted for Kerry again?Macneil Shonlehttps://www.blogger.com/profile/16382866616548432101noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1146704592134310922006-05-03T20:03:00.000-05:002006-05-03T20:03:00.000-05:00> Is it known how hard it is to find a 4-coloring ...> Is it known how hard it is to find a 4-coloring of a planar map?<BR/><BR/>The Robertson, Sanders, Seymour, and Thomas proof leads to a O(n^2) algorithm.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1146704359074302702006-05-03T19:59:00.000-05:002006-05-03T19:59:00.000-05:00Note that the four-color theorem doesn't apply dir...Note that the four-color theorem doesn't apply directly because of Michigan. :)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1146703886881280642006-05-03T19:51:00.000-05:002006-05-03T19:51:00.000-05:00It's in TFNP, so it can't be NP-complete unless NP...It's in TFNP, so it can't be NP-complete unless NP = coNP.<BR/><BR/>So the question is whether it is in P or possibly complete for a class like PPAD...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1146700623809506482006-05-03T18:57:00.000-05:002006-05-03T18:57:00.000-05:00Woops, that's to determine 3-colorability.Woops, that's to determine 3-colorability.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1146700390343290602006-05-03T18:53:00.000-05:002006-05-03T18:53:00.000-05:00Shown NP-complete by Stockmeyer in '73, says the f...Shown NP-complete by Stockmeyer in '73, says the first google hit to "4-coloring planar NP-complete".Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1146689231432152682006-05-03T15:47:00.000-05:002006-05-03T15:47:00.000-05:00Is it known how hard it is to find a 4-coloring of...Is it known how hard it is to find a 4-coloring of a planar map?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1146683137686358582006-05-03T14:05:00.000-05:002006-05-03T14:05:00.000-05:00>Most maps I found like this one >use five or more...>Most maps I found like this one <BR/>>use five or more colors, probably <BR/>>because they use a simple greedy <BR/>>algorithm.<BR/><BR/>I think they just do it "by hand"Osiashttps://www.blogger.com/profile/18342583333092991594noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1146682760979213792006-05-03T13:59:00.000-05:002006-05-03T13:59:00.000-05:00Every time we go to Z'Tejas (local Tex-Mex restaur...Every time we go to Z'Tejas (local Tex-Mex restaurant) my kids start four-coloring the map of the 48 contiguous states on the kids' paper placemats with the four crayon colors they hand out. As you say, it's not difficult as long as you work from one side to the other in a systematic order.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1146679303541760922006-05-03T13:01:00.000-05:002006-05-03T13:01:00.000-05:00Since you are also coloring Hawaii, it seems to me...Since you are also coloring Hawaii, it seems to me that you should color the states that are adjacent to the boundary with 3 colors Otherwise the colorings of the connected components are not consistent with each other (i.e. you cannot extend the coloring to a coloring of the globe).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1146676063358749122006-05-03T12:07:00.000-05:002006-05-03T12:07:00.000-05:00Are there any pair of states which must be the sam...Are there any pair of states which must be the same color?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1146672237900897642006-05-03T11:03:00.000-05:002006-05-03T11:03:00.000-05:00It is customary not to count the surrounding regio...It is customary not to count the surrounding region as needing a color. By the 4-color theorem if we don't require that Lake <BR/>Michigan have the same color as the Pacific/Atlantic coasts & Canadian/Mexican borders (and don't worry that some states look like lakes) then you should be able to reduce the color count in your diagram by one. Can you do that?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1146667528840585992006-05-03T09:45:00.000-05:002006-05-03T09:45:00.000-05:00Wikipedia has a nice four-color map of the US.<A HREF="http://en.wikipedia.org/wiki/Image:Map_of_USA_with_state_names.svg" REL="nofollow">Wikipedia</A> has a nice four-color map of the US.Nitishhttps://www.blogger.com/profile/07554352128342702471noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1146666198504495792006-05-03T09:23:00.000-05:002006-05-03T09:23:00.000-05:00Did you have to use red and blue? Geez. Cool pos...Did you have to use red and blue? Geez. Cool post, but I'm still instinctively turned off by red and blue maps of the US.Anonymousnoreply@blogger.com