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 $ 4$-color theorem for toroidal graphs


Authors: Hudson V. Kronk and Arthur T. White
Journal: Proc. Amer. Math. Soc. 34 (1972), 83-86
MSC: Primary 05C15
DOI: https://doi.org/10.1090/S0002-9939-1972-0291019-5
MathSciNet review: 0291019
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: It is well known that any graph imbedded in the torus has chromatic number at most seven, and that seven is attained by the graph $ {K_7}$. In this note we show that any toroidal graph containing no triangles has chromatic number at most four, and produce an example attaining this upper bound. The results are then extended for arbitrary girth.


References [Enhancements On Off] (What's this?)

  • [1] G. A. Dirac, A theorem of R. L. Brooks and a conjecture of H. Hadwiger, Proc. London Math. Soc. (3) 7 (1957), 161-195. MR 19, 161. MR 0086305 (19:161b)
  • [2] H. Grötzsch, Zur Theorie der diskreten Gebilde. VII. Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg. Math. Nat. Reihe 8 (1958/59), 109-120. MR 22 #7113c. MR 0116320 (22:7113c)
  • [3] F. Harary, Graph theory, Addison-Wesley, Reading, Mass., 1969. MR 41 #1566. MR 0256911 (41:1566)
  • [4] J. Mycielski, Sur le coloriage des graphs, Colloq. Math. 3 (1955), 161-162. MR 16, 1044. MR 0069494 (16:1044b)
  • [5] G. Szekeres and H. S. Wilf, An inequality for the chromatic number of a graph, J. Combinatorial Theory 4 (1968), 1-3. MR 36 #1356. MR 0218269 (36:1356)

Similar Articles

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

Retrieve articles in all journals with MSC: 05C15


Additional Information

DOI: https://doi.org/10.1090/S0002-9939-1972-0291019-5
Keywords: Graph, chromatic number, torus, girth
Article copyright: © Copyright 1972 American Mathematical Society

American Mathematical Society