Path: utzoo!attcan!uunet!ginosko!xanth!ames!apple!bbn!bbn.com!cosell
From: cosell@bbn.com (Bernie Cosell)
Newsgroups: comp.sys.amiga
Subject: Re: The four color problem (was Re: Re: Clicking on Irregular Shapes (and the four color problem))
Message-ID: <42421@bbn.COM>
Date: 9 Jul 89 04:26:43 GMT
References: <19250@louie.udel.EDU> <427@xdos.UUCP>
Sender: news@bbn.COM
Reply-To: cosell@BBN.COM (Bernie Cosell)
Organization: Bolt Beranek and Newman Inc., Cambridge MA
Lines: 35

In article <427@xdos.UUCP> doug@xdos.UUCP (Doug Merritt) writes:
}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  ...
}
}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.

No problem.  Since there is no *other* state separating the two parts of
michigan, you can make a modified US map with the Michigan and UP connected
by an infintessimal thread.  this thread will not cut any other state and so
you now have a normal, four-colorable map, and so you four color it.  the
thread will make the two parts of michigan act as a single connected region and
so be colored with a single hue, and then just use THAT coloring for the
original map.

Bodies of water are more complicated because unlike governmental
boundaries, they don't really start and end, but really just
interconnect to form huge serpentine regions that cut the land-regions
into assorted discontiguous shapes.  The entire Mississippi/Missouri
complex wouldhave to be a single color, and Louisiana, for example,
would be divided into a zillion not-connected pieces.  I suspect,
though, that even with considering connected bodies of water as regions
(even though that gives you disconnected land regions), you can still
four-color the whole mess.  I'm *sure* that if you consider ALL bodies
of water as a *single* (of necessity disconnected) region, then you're
sunk.

  /Bernie\