A $4$-color theorem for toroidal graphs
HTML articles powered by AMS MathViewer
- by Hudson V. Kronk and Arthur T. White PDF
- Proc. Amer. Math. Soc. 34 (1972), 83-86 Request permission
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
- 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 86305, DOI 10.1112/plms/s3-7.1.161
- Herbert Grötzsch, Zur Theorie der diskreten Gebilde. V. Beziehungen zwischen Vierkant- und Dreikantnetzen auf der Kugel, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 7 (1958), 353–358 (German). MR 116318
- Frank Harary, Graph theory, Addison-Wesley Publishing Co., Reading, Mass.-Menlo Park, Calif.-London 1969. MR 0256911
- J. Mycielski, Sur le coloriage des graphs, Colloq. Math. 3 (1955), 161–162 (French). MR 69494, DOI 10.4064/cm-3-2-161-162
- G. Szekeres and Herbert S. Wilf, An inequality for the chromatic number of a graph, J. Combinatorial Theory 4 (1968), 1–3. MR 218269
Additional Information
- © Copyright 1972 American Mathematical Society
- 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