Some 3- and 4-color theorems for the plane,
the projective plane,
and the torus;
or
Variations on some themes of Heawood and Hadwiger.
Joan P. Hutchinson
Professor of Mathematics and Computer Science
Macalester College
In 1890 P. J. Heawood asserted that every planar
triangulation with all vertices
of even degree could be three-colored and that "The proof of this is not
difficult, but it appears to shed no light on the main proposition [the
four-color problem] ..." We explore implications of one proof of the above
three-color theorem to obtain a four-color theorem for some classes of
graphs on the plane, on the pinched
torus, and on the projective plane (without use of the
four-color theorem). The latter yields a special case of Hadwiger's conjecture;
in general Hadwiger conjectured that a k-chromatic graph contracts to the
complete graph on k vertices. With Karen Collins we also investigate colorings
of even triangulations of the torus and six-regular triangulations, in
particular. We prove, for example, that a standard mxn 6-regular grid on the
torus can be four-colored if 3 <= m <= n.
figure appears below:
<\center>