A five-color theorem for graphs on surfaces

Hutchinson, Joan P.

doi:10.1090/S0002-9939-1984-0728376-7

A five-color theorem for graphs on surfaces
HTML articles powered by AMS MathViewer

by Joan P. Hutchinson PDF

Proc. Amer. Math. Soc. 90 (1984), 497-504 Request permission

Abstract:

We prove that if a graph embeds on a surface with all edges suitably short, then the vertices of the graph can be five-colored. The motivation is that a graph embedded with short edges is locally a planar graph and hence should not require many more than four colors.

References

Michael O. Albertson and Joan P. Hutchinson, On the independence ratio of a graph, J. Graph Theory 2 (1978), no. 1, 1–8. MR 491281, DOI 10.1002/jgt.3190020102
Michael O. Albertson and Joan P. Hutchinson, Hadwiger’s conjecture and six-chromatic toroidal graphs, Graph theory and related topics (Proc. Conf., Univ. Waterloo, Waterloo, Ont., 1977) Academic Press, New York-London, 1979, pp. 35–40. MR 538034
Michael O. Albertson and Walter R. Stromquist, Locally planar toroidal graphs are $5$-colorable, Proc. Amer. Math. Soc. 84 (1982), no. 3, 449–457. MR 640251, DOI 10.1090/S0002-9939-1982-0640251-3
K. Appel and W. Haken, Every planar map is four colorable, Bull. Amer. Math. Soc. 82 (1976), no. 5, 711–712. MR 424602, DOI 10.1090/S0002-9904-1976-14122-5
Béla Bollobás, Graph theory, Graduate Texts in Mathematics, vol. 63, Springer-Verlag, New York-Berlin, 1979. An introductory course. MR 536131
P. Erdős, Graph theory and probability. II, Canadian J. Math. 13 (1961), 346–352. MR 120168, DOI 10.4153/CJM-1961-029-9
Maurice Fréchet and Ky Fan, Initiation to combinatorial topology, Prindle, Weber & Schmidt, Inc., Boston, Mass.-London-Sydney, 1967. Translated from the French, with some notes, by Howard W. Eves. MR 0210057
John R. Gilbert, Joan P. Hutchinson, and Robert Endre Tarjan, A separator theorem for graphs of bounded genus, J. Algorithms 5 (1984), no. 3, 391–407. MR 756165, DOI 10.1016/0196-6774(84)90019-1
Branko Grünbaum, Grötzsch’s theorem on $3$-colorings, Michigan Math. J. 10 (1963), 303–310. MR 154274
Joan P. Hutchinson, On coloring maps made from Eulerian graphs, Proceedings of the Fifth British Combinatorial Conference (Univ. Aberdeen, Aberdeen, 1975) Congressus Numerantium, No. XV, Utilitas Math., Winnipeg, Man., 1976, pp. 343–354. MR 0398877
Elisabeth Kaiser, Färbungssätze für Graphen auf der projektiven Ebene, dem Torus und dem Kleinschen Schlauch, Wiss. Z. Tech. Hochsch. Ilmenau 20 (1974), no. 1, 47–53 (German). MR 344154
Hudson V. Kronk, The chromatic number of triangle-free graphs, Graph theory and applications (Proc. Conf., Western Michigan Univ., Kalamazoo, Mich., 1972; dedicated to the memory of J. W. T. Youngs), Lecture Notes in Math., Vol. 303, Springer, Berlin, 1972, pp. 179–181. MR 0335332
Hudson V. Kronk and Arthur T. White, A $4$-color theorem for toroidal graphs, Proc. Amer. Math. Soc. 34 (1972), 83–86. MR 291019, DOI 10.1090/S0002-9939-1972-0291019-5
Gerhard Ringel and J. W. T. Youngs, Solution of the Heawood map-coloring problem, Proc. Nat. Acad. Sci. U.S.A. 60 (1968), 438–445. MR 228378, DOI 10.1073/pnas.60.2.438

Introduction to Riemann surfaces

Graphs, groups and surfaces