Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

Remote Access
Green Open Access
Transactions of the American Mathematical Society
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 Free Access

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?)

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

PII: S 0002-9947(97)01926-0
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