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)



Locally planar toroidal graphs are $ 5$-colorable

Authors: Michael O. Albertson and Walter R. Stromquist
Journal: Proc. Amer. Math. Soc. 84 (1982), 449-457
MSC: Primary 05C10; Secondary 05C15
MathSciNet review: 640251
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: If a graph can be embedded in a torus in such a way that all noncontractible cycles have length at least 8, then its vertices may be $ 5$-colored. The conclusion remains true when some noncontractible cycles have length less than 8, if the exceptions are all homotopic. Essentially this hypothesis means that small neighborhoods of the graph are planar. No similar conclusion holds for $ 4$-colorability.

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

Similar Articles

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

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

Additional Information

Keywords: Toroidal graph, vertex coloring
Article copyright: © Copyright 1982 American Mathematical Society