Re: Map Colors (was: Re: New <AREA> syntax proposal)

On Tue, 10 Jun 1997 jwp@checfs1.ucsd.edu wrote:

> I haven't got a clue what this discussion is doing here, but...

It's a bizarre place to start discussing graph theory, but ...

> Four colors is the maximum number of colors needed to color a "map" of any
> number of regions (in the plane) of any shape in such a way that no regions
> of the same color share a common border. ("Border" is defined as touching
> at more than a single point.

This is known as "four face-colouring", for fairly obvious reasons.

> This was a very famous, long-standing problem
> in topology. Actually, mapmakers had "known" more-or-less forever that they
> only needed four colors. The problem was to *prove* that only four were needed
> (or, obviously, to prove that there were "maps" that needed more than four).
> I've forgotten when the problem was posed (Euler era? Before?)

Actually the four colour problem was first proposed in 1852 by Francis
Guthrie (spelling?). There were a number of incorrect attempts at proving
it during the nineteenth century, most if not all disproved by the turn of
the century.

> but it floated
> around for three hundred years or so with billions of people doing incorrect
> proofs (rather like the problem of squaring the circle, or Fermat's Last
> Theorem). It was finally proven that four are enough by (I think) two
> mathematicians in (I think) the late '60s or early '70s,

Appel and Haken in 1976.

> who did it (if I
> remember correctly) by proving that there are only some finite number of
> (topologically) different maps (four or five hundred, I believe) and then
> using a computer to exhaustively test all of them.

That sounds about right, yes.

>  > But what about a simple chess board?
>  > 
>  > No; I think 4 colors is the maximum EVER needed for ANY maps.

Well, depending on your definition of a map. For any map which can be
drawn in the plane (equivalent to drawing it on the sphere, and hence on
the orientable surface of genus zero) you need at most four colours. The
theory can be extended for orientable surfaces of higher genus, but I
don't know how much of it has been proved.

Chessboard colouring:

3 4 1 2 3 4 1 2
1 2 3 4 1 2 3 4
3 4 1 2 3 4 1 2
1 2 3 4 1 2 3 4
3 4 1 2 3 4 1 2
1 2 3 4 1 2 3 4
3 4 1 2 3 4 1 2
1 2 3 4 1 2 3 4

which tesselates infinitly.

James

-- 
/--------------------------------------------------------------------------\
   James Aylett -- Crystal Services (crystal.clare.cam.ac.uk) Ftp and Web
         Clare College, Cambridge, CB2 1TL  -- james.aylett@usa.net

Received on Wednesday, 11 June 1997 08:36:37 UTC