[ Editor: Has the four-color map problem been solved, and what about coloring maps on surfaces of higher genus, such as the torus?

In article <56u7ip$8ld@sjx-ixn6.ix.netcom.com>, Fred W. Helenius
<fredh@ix.netcom.com> writes:

>>Finally, and I think this was in the 50's or 60's, a generally
>>accepted proof was published, and the matter has been at rest, at
>>least fundamentally, since then.
>
>Appel and Haken, 1976.  Their proof, still controversial in some
>quarters, required a computer-based check of a thousand or so
>subcases.  Other proofs (simpler, but still requiring computer
>assistance) have appeared more recently.

Regarding the higher genus question, *that* problem was solved in the
sixties, before its more infamous genus 0 cousin.  It turns out to
have a long and tedious but still human readable proof.  See Gerhard
Ringel, [ Editor: no comma in the original ] MAP COLOR THEOREM (Springer-Verlag 1974) for the details.

In a humorous reversal to the 4-color map problem itself, it was
fairly easy to prove the conjectured upper bound, a peculiar looking
formula involving solving a quadratic for the number of colors, and
indeed this formula and its proof can be found in many graph theory
texts.  (And which formula tantalizingly gives 4 for genus 0, but the
proof does not apply.)

What was so difficult was to actually construct worst case maps.  For
any particular surface somebody studied, like the torus, the two-holed
torus, etc., [ Editor: "etc," in the original ] it was not too hard, so proofs for these surfaces were
known decades before Appel & Haken, but finding the general pattern
was rather hard.  It turned out to break down into 12 distinct cases!

-- Matthew P Wiener <weemba@sagi.wistar.upenn.edu>