Coloring graphs with fixed genus and girth
Authors:
- John GimbelJGJohn Gimbel
- Carsten ThomassenCTCarsten Thomassen
Open Access
- 1 November 1997
- journal article
- Published by American Mathematical Society (AMS) in Transactions of the American Mathematical Society
- Vol. 349 (11) , 4555-4564
Abstract
It is well known that the maximum chromatic number of a graph on the orientable surface S g S_g is θ ( g 1 / 2 ) \theta (g^{1/2}) . We prove that there are positive constants c 1 , c 2 c_1,c_2 such that every triangle-free graph on S g S_g has chromatic number less than c 2 ( g / log ( g ) ) 1 / 3 c_2(g/\log (g))^{1/3} and that some triangle-free graph on S g S_g has chromatic number at least c 1 g 1 / 3 log ( g ) c_1\frac {g^{1/3}}{\log (g)} . We obtain similar results for graphs with restricted clique number or girth on S g S_g or N k N_k . As an application, we prove that an S g S_g -polytope has chromatic number at most O ( g 3 / 7 ) 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.Keywords
This publication has 15 references indexed in Scilit:
- Some extremal results in cochromatic and dichromatic theoryJournal of Graph Theory, 1991
- A Dense Infinite Sidon SequenceEuropean Journal of Combinatorics, 1981
- A note on Ramsey numbersJournal of Combinatorial Theory, Series A, 1980
- Note on the cochromatic number of several surfacesJournal of Graph Theory, 1980
- Cochromatic Number and the Genus of a GraphJournal of Graph Theory, 1979
- Some simplified NP-complete graph problemsTheoretical Computer Science, 1976
- Chromatic number and girthPeriodica Mathematica Hungarica, 1975
- A 4-Color Theorem for Toroidal GraphsProceedings of the American Mathematical Society, 1972
- Graph Theory and Probability. IICanadian Journal of Mathematics, 1961
- On Frobeniusean Algebras. IAnnals of Mathematics, 1939