Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!apple!motcsd!xdos!doug
From: doug@xdos.UUCP (Doug Merritt)
Newsgroups: comp.sys.amiga
Subject: Re: The four color problem (was Re: Re: Clicking on Irregular Shapes (and the four color problem))
Message-ID: <427@xdos.UUCP>
Date: 8 Jul 89 17:03:51 GMT
References: <19250@louie.udel.EDU>
Reply-To: doug@xdos.UUCP (Doug Merritt)
Organization: Hunter Systems, Mountain View CA (Silicon Valley)
Lines: 27

In article <19250@louie.udel.EDU> "kosma@ALAN.LAAC-AI.Dialnet.Symbolics.COM"@alan.kahuna.decnet.lockheed.com writes:
>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.

Good point. I screwed up in my previous posting on the subject, because
I was thinking about Alaska and Hawaii as the "noncontiguous" portions,
and they do *not* cause problems. You can still 4-color such a map,
even including using one of the four colors for the ocean.

What can cause a problem is the example in another posting of a state
split by a great lake (Michigan)...both halves of the state must be the same
color, and this additional constraint could make the map non-4-colorable,
depending on surrounding configurations.

Looking at a map of the US, it's difficult to see whether Michigan
is in fact a problematic configuration, but it may be.
	Doug
-- 
Doug Merritt		{pyramid,apple}!xdos!doug
Member, Crusaders for a Better Tomorrow		Professional Wildeyed Visionary