Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



Coloring graphs with fixed genus and girth

Authors: John Gimbel and Carsten Thomassen
Journal: Trans. Amer. Math. Soc. 349 (1997), 4555-4564
MSC (1991): Primary 05C10
MathSciNet review: 1422897
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: It is well known that the maximum chromatic number of a graph on the orientable surface $S_g$ is $\theta (g^{1/2})$. We prove that there are positive constants $c_1,c_2$ such that every triangle-free graph on $S_g$ has chromatic number less than $c_2(g/\log (g))^{1/3}$ and that some triangle-free graph on $S_g$ has chromatic number at least $c_1\frac {g^{1/3}}{\log (g)}$. We obtain similar results for graphs with restricted clique number or girth on $S_g$ or $N_k$. As an application, we prove that an $S_g$-polytope has chromatic number at most $O(g^{3/7})$. For specific surfaces we prove that every graph on the double torus and of girth at least six is 3-colorable and we characterize completely those triangle-free projective graphs that are not 3-colorable.

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

  • 1. M. Ajtai, J. Komlós, and E. Szemerédi, A note on Ramsey numbers, J. Combinatorial Theory (A) 29 (1980), 354-360. MR 82a:05064
  • 2. -, A dense infinite Sidon sequence, Europ. J. Combinatorics 2 (1981), 1-11. MR 83f:10056
  • 3. B. Bollobás, Random Graphs, Academic Press, London, 1985. MR 87f:05152
  • 4. G. Chartrand and L. Lesniak, Graphs and Digraphs, 2nd ed., Wadsworth & Brooks/Cole, Monterey, 1986. MR 87h:05001
  • 5. R. J. Cook, Chromatic number and girth, Period. Math. Hungar. 6 (1975), 103-107. MR 52:163
  • 6. H. T. Croft, K. J. Falconer and R. K. Guy, Unsolved problems in geometry, Springer-Verlag, 1991. MR 92c:52001
  • 7. P. Erdös, Graph theory and probability, Canad. J. Math. 11 (1959), 34-38.
  • 8. -, Graph theory and probability. II, Canad. J. Math. 13 (1961), 346-352. MR 22:10925
  • 9. P.Erdös, J. Gimbel and D. Kratsch, Some extremal results in cochromatic and dichromatic theory, J. Graph Theory 15 (1991), 579-585. MR 92i:05118
  • 10. S. Fisk and B. Mohar, Coloring graphs without short nonbounding cycles, J. Comb. Theory (B) 60 (1994), 268-276. MR 95b:05073
  • 11. T. Gallai, Kritische Graphen I, II, Publ. Math. Inst. Hungar. Acad. Sci. 8 (1963), 165-192 and 373-395. MR 32:5540; MR 32:5541.
  • 12. M. R. Garey, D. S. Johnson, and L. Stockmeyer, Some simplified NP-complete graph problems, Theor. Comput. Sci. 1 (1976), 237-267. MR 53:14978
  • 13. J. Gimbel, Three extremal problems in cochromatic theory, Rostock. Math. Kolloq. 30 (1986), 73-78. MR 88d:05060
  • 14. H. Grötzsch, Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg. Mat.-Nat. Reihe 8 (1958), 109-129. MR 22:7113c
  • 15. G. Hajós, Über eine konstruktion nicht $n$-färbarer graphen, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg. Math.-Nat. Reihe 10 (1961), 116-117.
  • 16. R. H. Kim, The Ramsey number $R(3,t)$ has order of magnitude $t^2/\log (t)$. Preprint.
  • 17. H. V. Kronk, The chromatic number of triangle-free graphs, in Y. Alavi, D. R. Lick and
    A. T. White, editors, Graph Theory and Applications, Lecture Notes in Mathematics, Vol. 303, Springer-Verlag, 1972, pp. 179-181. MR 49:114
  • 18. H. V. Kronk and A. T. White, A $4$-color theorem for toroidal graphs, Proc. Amer. Math. Soc. 34 (1972), 83-86. MR 45:113
  • 19. B. Mohar and C. Thomassen, Graphs on surfaces, Johns Hopkins University Press, Baltimore (to appear).
  • 20. J. Mycielski, Sur les coloriage des graphs, Colloq. Math. 3 (1955), 161-162. MR 16:1044b
  • 21. H. J. Straight, Cochromatic number and genus of a graph, J. Graph Theory 3 (1979), 43-51. MR 80b:05030
  • 22. -, Note on the cochromatic number of several surfaces, J. Graph Theory 4 (1980), 115-117. MR 81e:05063
  • 23. C. Thomassen, Grötzsch's $3$-color theorem and its counterparts for the torus and the projective plane, J. Comb. Theory (B) 62 (1994), 268-279. MR 95j:05098
  • 24. -, Color critical graphs on a fixed surface, to appear.
  • 25. D. A. Youngs, $4$-chromatic projective graphs, J. Graph Theory 21 (1996), 219-227. MR 96h:05081
  • 26. M. Albertson and J. Hutchinson, The three excluded cases of Dirac's map-color theorem, Ann. New York Acad. Sci. 319 (1979), 7-17. MR 81c:05037

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (1991): 05C10

Retrieve articles in all journals with MSC (1991): 05C10

Additional Information

John Gimbel
Affiliation: Department of Mathematical Sciences, University of Alaska, Fairbanks, Alaska 99775

Carsten Thomassen
Affiliation: Mathematical Institute, Building 303, Technical University of Denmark, 2800 Lyngby, Denmark

Received by editor(s): January 1, 1996
Additional Notes: Funding for this project was generously provided by The Technical University of Denmark, Special Initiative on Mathematical Modelling of Computer-Based Systems.
Article copyright: © Copyright 1997 American Mathematical Society

American Mathematical Society