Path: utzoo!utgpu!watmath!iuvax!cica!gatech!udel!mmdf From: "kosma@ALAN.LAAC-AI.Dialnet.Symbolics.COM"@alan.kahuna.decnet.lockheed.com Newsgroups: comp.sys.amiga Subject: The four color problem (was Re: Re: Clicking on Irregular Shapes (and the four color problem)) Message-ID: <19250@louie.udel.EDU> Date: 8 Jul 89 01:37:42 GMT Sender: mmdf@udel.EDU Lines: 59 Received: from GEORG.LAAC-AI.Dialnet.Symbolics.COM by ALAN.LAAC-AI.Dialnet.Symbolics.COM via CHAOS with CHAOS-MAIL id 28908; Fri 7-Jul-89 14:32:47 PDT Date: Fri, 7 Jul 89 14:32 PDT From: Montgomery Kosma Subject: The four color problem (was Re: Re: Clicking on Irregular Shapes (and the four color problem)) To: "eagle::amiga-relay%udel.edu"@KAHUNA.LAAC-AI.Dialnet.Symbolics.COM In-Reply-To: Your message of 7 Jul 89 14:12 PDT Message-ID: <19890707213242.8.KOSMA@GEORG.LAAC-AI.Dialnet.Symbolics.COM> In article <54160@tut.cis.ohio-state.edu> Jeff Martens writes : Probably not good maps then -- the US is not 4-colorable. Consider West Virginia, Ohio, and Wyoming, for example. They each have more than 4 neighbors. A map's "goodness" may be a rather subjective measure but if what you refer to is the ability to color a map without having neighboring states/areas using the same color, it seems that you missed something. A state having more than four neighbors does NOT mean that it requires MORE than four colors to prevent neighboring states from having the same color. For example, imaging the following state FOO which has several neighbors as sketched below: BAR --- XYZZY --- PLUGH | \ | / | | FOO | | / | \ | FROOP ----------- SCUMDOGGIE clearly (well, somewhat clearly) FOO has 5 neighbors. Now, imagine colors indexed from 0 to 3...this arrangement can be colored as follows: 0 1 2 3 1 0 It's rather easy to see that with a simple case like this only four colors are needed. Now I'm not positive of all the aspects of it, but the four color theorem says basically that four colors are enough for maps which do not have such features as non-contiguous regions (and the example usually given is of a region which has two parts, one of which is enclosed by another region--like when you want to color the space around a doughnut and the space in the hole of the doughnut the same color). I don't know if this causes a problem when coloring the US--I suspect that if you allow one further color for bodies of water, then four colors for all of the states will suffice. Montgomery N. Kosma disclaimer: this has nothing to do with Lockheed--I'm just hanging around saving a world on one of my lispms.