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>