Skip to Main Content

Proceedings of the American Mathematical Society

Published by the American Mathematical Society since 1950, Proceedings of the American Mathematical Society is devoted to shorter research articles in all areas of pure and applied mathematics.

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

The 2020 MCQ for Proceedings of the American Mathematical Society is 0.85.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

Locally planar toroidal graphs are $5$-colorable
HTML articles powered by AMS MathViewer

by Michael O. Albertson and Walter R. Stromquist PDF
Proc. Amer. Math. Soc. 84 (1982), 449-457 Request permission

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
  • 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
  • K. Appel and W. Haken, Every planar map is four colorable. I. Discharging, Illinois J. Math. 21 (1977), no. 3, 429–490. MR 543792
  • K. Appel and W. Haken, Every planar map is four colorable. I. Discharging, Illinois J. Math. 21 (1977), no. 3, 429–490. MR 543792
  • G. A. Dirac, Short proof of a map-colour theorem, Canadian J. Math. 9 (1957), 225. MR 86306, DOI 10.4153/CJM-1957-027-2
  • Steve Fisk, The nonexistence of colorings, J. Combinatorial Theory Ser. B 24 (1978), no. 2, 247–248. MR 491299, DOI 10.1016/0095-8956(78)90028-x
    • P. J. Heawood, Map-colour theorem, Quart J. Pure Appl. Math. 24 (1890), 332-338.
  • Roy B. Levow, Coloring planar graphs with five or more colors, Proceedings of the Fifth Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1974), Congressus Numerantium, No. X, Utilitas Math., Winnipeg, Man., 1974, pp. 549–561. MR 0357202
  • H. Joseph Straight, Note on the cochromatic number of several surfaces, J. Graph Theory 4 (1980), no. 1, 115–117. MR 558460, DOI 10.1002/jgt.3190040114
    • W. Stromquist, The four color problem for locally planar graphs, Graph Theory and Related Topics, Academic Press, New York, 1979, pp. 369-370.
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
  • © Copyright 1982 American Mathematical Society
  • Journal: Proc. Amer. Math. Soc. 84 (1982), 449-457
  • MSC: Primary 05C10; Secondary 05C15
  • DOI: https://doi.org/10.1090/S0002-9939-1982-0640251-3
  • MathSciNet review: 640251