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.
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