Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 
 

 

A five-color theorem for graphs on surfaces


Author: Joan P. Hutchinson
Journal: Proc. Amer. Math. Soc. 90 (1984), 497-504
MSC: Primary 05C15; Secondary 05C10
DOI: https://doi.org/10.1090/S0002-9939-1984-0728376-7
MathSciNet review: 728376
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] M. O. Albertson and J. P. Hutchinson, On the independence ratio of a graph, J. Graph Theory 2 (1978), 1-8. MR 0491281 (58:10545a)
  • [2] -, On six-chromatic toroidal graphs, Proc. London Math. Soc. 41 (1980), 533-556. MR 591654 (82k:05047b)
  • [3] M. O. Albertson and W. R. Stromquist, Locally planar toroidal graphs are $ 5$-colorable, Proc. Amer. Math. Soc. 84 (1982), 449-456. MR 640251 (83a:05053)
  • [4] K. Appell and W. Haken, Every planar map is four-colorable, Bull. Amer. Math. Soc. 82 (1976), 711-712. MR 0424602 (54:12561)
  • [5] B. Bollobas, Graph theory, an introductory course, Springer-Verlag, New York, 1979. MR 536131 (80j:05053)
  • [6] P. Erdös, Graph theory and probability. II, Canad. J. Math. 13 (1961), 346-352. MR 0120168 (22:10925)
  • [7] M. Fréchet and K. Fan, Initiation to combinatorial topology, Prindle, Weber and Schmidt, Boston, Mass., 1967. MR 0210057 (35:952)
  • [8] J. R. Gilbert, J. P. Hutchinson and R. E. Tarjan, A separator theorem for graphs of bounded genus, J. Algorithms (to appear). MR 756165 (86h:68145)
  • [9] B. Grünbaum, Grötzsch's theorem on $ 3$-colorings, Michigan Math. J. 10 (1963), 303-310. MR 0154274 (27:4223)
  • [10] J. P. Hutchinson, On coloring maps made from Eulerian graphs, Proc. Fifth British Combinatorial Conf. (Univ. of Aberdeen), 1975, pp. 343-354. MR 0398877 (53:2728)
  • [11] E. Kaiser, Färbungssätze für Graphen auf der projektiven Ebene, dem Torus und dem Kleinschen Schlauch, Wiss. Tech. Hochsch. Ilmenau 20 (1974), 47-53. MR 0344154 (49:8894)
  • [12] H. V. Kronk, The chromatic number of triangle-free graphs, Graph Theory and Applications (Proc. Conf., Western Michigan Univ., Kalamazoo, Mich., 1972), Lecture Notes in Math., vol. 303, Springer, Berlin, 1972, pp. 179-181. MR 0335332 (49:114)
  • [13] H. V. Kronk and A. T. White, A $ 4$-color theorem for toroidal graphs, Proc. Amer. Math. Soc. 34 (1972), 83-86. MR 0291019 (45:113)
  • [14] J. Mycielski, personal communication.
  • [15] G. 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 0228378 (37:3959)
  • [16] G. Springer, Introduction to Riemann surfaces, Chelsea, New York, 1981.
  • [17] W. R. Stromquist, personal communication.
  • [18] A. T. White, Graphs, groups and surfaces, North-Holland, Amsterdam, 1973.

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC: 05C15, 05C10

Retrieve articles in all journals with MSC: 05C15, 05C10


Additional Information

DOI: https://doi.org/10.1090/S0002-9939-1984-0728376-7
Keywords: Vertex coloring, embedded graph
Article copyright: © Copyright 1984 American Mathematical Society

American Mathematical Society