Locally planar toroidal graphs are colorable
Authors:
Michael O. Albertson and Walter R. Stromquist
Journal:
Proc. Amer. Math. Soc. 84 (1982), 449457
MSC:
Primary 05C10; Secondary 05C15
MathSciNet review:
640251
Fulltext 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 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
(58 #10545a)
 [2]
Michael
O. Albertson and Joan
P. Hutchinson, On sixchromatic toroidal graphs, Proc. London
Math. Soc. (3) 41 (1980), no. 3, 533–556. MR 591654
(82k:05047b), http://dx.doi.org/10.1112/plms/s341.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
(58 #27598a)
 [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
(58 #27598b)
 [5]
G.
A. Dirac, Short proof of a mapcolour theorem, Canad J. Math.
9 (1957), 225. MR 0086306
(19,161c)
 [6]
Steve
Fisk, The nonexistence of colorings, J. Combinatorial Theory
Ser. B 24 (1978), no. 2, 247–248. MR 0491299
(58 #10562)
 [7]
P. J. Heawood, Mapcolour theorem, Quart J. Pure Appl. Math. 24 (1890), 332338.
 [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
(50 #9670)
 [9]
H.
Joseph Straight, Note on the cochromatic number of several
surfaces, J. Graph Theory 4 (1980), no. 1,
115–117. MR
558460 (81e:05063), http://dx.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. 369370.
 [1]
 M. O. Albertson and J. P. Hutchinson, On the independence ratio of a graph, J. Graph Theory 2 (1978), 18. MR 0491281 (58:10545a)
 [2]
 , On sixchromatic toroidal graphs, Proc. London Math. Soc. (3) 41 (1980), 533556. MR 591654 (82k:05047b)
 [3]
 K. Appel and W. Haken, Every planar map is four colorable. Part I: Discharging, Illinois J. Math. 21 (1977), 429490. MR 0543792 (58:27598a)
 [4]
 K. Appel, W. Haken and J. Koch, Every planar map is four colorable. Part II: Reducibility, Illinois J. Math. 21 (1977), 491567. MR 0543793 (58:27598b)
 [5]
 G. A. Dirac, Short proof of a map colour theorem, Canad. J. Math. 9 (1957), 225226. MR 0086306 (19:161c)
 [6]
 S. Fisk, The nonexistence of colorings, J. Combin. Theory Ser. B 24 (1978), 247248. MR 0491299 (58:10562)
 [7]
 P. J. Heawood, Mapcolour theorem, Quart J. Pure Appl. Math. 24 (1890), 332338.
 [8]
 R. B. Levow, Coloring planar graphs with five or more colors, Proc. 5th S.E. Conf. Combinatorics, Graph Theory, and Computing, Utilitas Math. Publ., Winnepeg, 1974, pp. 549561. MR 0357202 (50:9670)
 [9]
 H. J. Straight, Note on the cochromatic number of several surfaces, J. Graph Theory 4 (1980), 115117. MR 558460 (81e:05063)
 [10]
 W. Stromquist, The four color problem for locally planar graphs, Graph Theory and Related Topics, Academic Press, New York, 1979, pp. 369370.
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
DOI:
http://dx.doi.org/10.1090/S00029939198206402513
PII:
S 00029939(1982)06402513
Keywords:
Toroidal graph,
vertex coloring
Article copyright:
© Copyright 1982
American Mathematical Society
