Locally planar toroidal graphs are -colorable

Authors:
Michael O. Albertson and Walter R. Stromquist

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

Full-text PDF

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

**[1]**Michael O. Albertson and Joan P. Hutchinson,*On the independence ratio of a graph*, J. Graph Theory**2**(1978), no. 1, 1–8. MR**0491281**, https://doi.org/10.1002/jgt.3190020102**[2]**Michael O. Albertson and Joan P. Hutchinson,*On six-chromatic toroidal graphs*, Proc. London Math. Soc. (3)**41**(1980), no. 3, 533–556. MR**591654**, https://doi.org/10.1112/plms/s3-41.3.533**[3]**K. Appel and W. Haken,*Every planar map is four colorable. I. Discharging*, Illinois J. Math.**21**(1977), no. 3, 429–490. MR**0543792****[4]**K. Appel, W. Haken, and J. Koch,*Every planar map is four colorable. II. Reducibility*, Illinois J. Math.**21**(1977), no. 3, 491–567. MR**0543793****[5]**G. A. Dirac,*Short proof of a map-colour theorem*, Canad J. Math.**9**(1957), 225. MR**0086306**, https://doi.org/10.4153/CJM-1957-027-2**[6]**Steve Fisk,*The nonexistence of colorings*, J. Combinatorial Theory Ser. B**24**(1978), no. 2, 247–248. MR**0491299****[7]**P. J. Heawood,*Map-colour theorem*, Quart J. Pure Appl. Math.**24**(1890), 332-338.**[8]**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), Utilitas Math., Winnipeg, Man., 1974, pp. 549–561. Congressus Numerantium, No. X. MR**0357202****[9]**H. Joseph Straight,*Note on the cochromatic number of several surfaces*, J. Graph Theory**4**(1980), no. 1, 115–117. MR**558460**, https://doi.org/10.1002/jgt.3190040114**[10]**W. Stromquist,*The four color problem for locally planar graphs*, Graph Theory and Related Topics, Academic Press, New York, 1979, pp. 369-370.

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

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

Additional Information

DOI:
https://doi.org/10.1090/S0002-9939-1982-0640251-3

Keywords:
Toroidal graph,
vertex coloring

Article copyright:
© Copyright 1982
American Mathematical Society