×

zbMATH — the first resource for mathematics

Coloring graphs with fixed genus and girth. (English) Zbl 0884.05039
Summary: 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.

MSC:
05C10 Planar graphs; geometric and topological aspects of graph theory
05C15 Coloring of graphs and hypergraphs
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Miklós Ajtai, János Komlós, and Endre Szemerédi, A note on Ramsey numbers, J. Combin. Theory Ser. A 29 (1980), no. 3, 354 – 360. · Zbl 0455.05045 · doi:10.1016/0097-3165(80)90030-8 · doi.org
[2] Miklós Ajtai, János Komlós, and Endre Szemerédi, A dense infinite Sidon sequence, European J. Combin. 2 (1981), no. 1, 1 – 11. · Zbl 0474.10038 · doi:10.1016/S0195-6698(81)80014-5 · doi.org
[3] Béla Bollobás, Random graphs, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], London, 1985. · Zbl 0567.05042
[4] Gary Chartrand and Linda Lesniak, Graphs and digraphs, 2nd ed., The Wadsworth & Brooks/Cole Mathematics Series, Wadsworth & Brooks/Cole Advanced Books & Software, Monterey, CA, 1986. · Zbl 0666.05001
[5] R. J. Cook, Chromatic number and girth, Period. Math. Hungar. 6 (1975), 103 – 107. · Zbl 0313.05107 · doi:10.1007/BF02018401 · doi.org
[6] Hallard T. Croft, Kenneth J. Falconer, and Richard K. Guy, Unsolved problems in geometry, Problem Books in Mathematics, Springer-Verlag, New York, 1991. Unsolved Problems in Intuitive Mathematics, II. · Zbl 0748.52001
[7] P. Erdös, Graph theory and probability, Canad. J. Math. 11 (1959), 34-38. · Zbl 0084.39602
[8] P. Erdős, Graph theory and probability. II, Canad. J. Math. 13 (1961), 346 – 352. · Zbl 0097.39102 · doi:10.4153/CJM-1961-029-9 · doi.org
[9] Paul Erdős, John Gimbel, and Dieter Kratsch, Some extremal results in cochromatic and dichromatic theory, J. Graph Theory 15 (1991), no. 6, 579 – 585. · Zbl 0743.05047 · doi:10.1002/jgt.3190150604 · doi.org
[10] Steve Fisk and Bojan Mohar, Coloring graphs without short nonbounding cycles, J. Combin. Theory Ser. B 60 (1994), no. 2, 268 – 276. · Zbl 0793.05058 · doi:10.1006/jctb.1994.1018 · doi.org
[11] T. Gallai, Kritische Graphen. I, Magyar Tud. Akad. Mat. Kutató Int. Közl. 8 (1963), 165 – 192 (German, with Russian summary). T. Gallai, Kritische Graphen. II, Magyar Tud. Akad. Mat. Kutató Int. Közl. 8 (1963), 373 – 395 (1964) (German, with Russian summary).
[12] M. R. Garey, D. S. Johnson, and L. Stockmeyer, Some simplified NP-complete graph problems, Theoret. Comput. Sci. 1 (1976), no. 3, 237 – 267. · Zbl 0338.05120 · doi:10.1016/0304-3975(76)90059-1 · doi.org
[13] John Gimbel, Three extremal problems in cochromatic theory, Rostock. Math. Kolloq. 30 (1986), 73 – 78. · Zbl 0617.05030
[14] Herbert Grötzsch, Zur Theorie der diskreten Gebilde. V. Beziehungen zwischen Vierkant- und Dreikantnetzen auf der Kugel, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg. Math.-Nat. Reihe 7 (1958), 353 – 358 (German). Herbert Grötzsch, Zur Theorie der diskreten Gebilde. VI. Ein Kantentransformationssatz für gerade Dreikantnetze mit Viereckssystem auf der Kugel, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg. Math.-Nat. Reihe 7 (1958), 447 – 456 (German). Herbert Grötzsch, Zur Theorie der diskreten Gebilde. VII. Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg. Math.-Nat. Reihe 8 (1958/1959), 109 – 120 (German). Herbert Grötzsch, Zur Theorie der diskreten Gebilde. VIII. Transformation modulo 2 und modulo 3 von Netzen, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg. Math.-Nat. Reihe 8 (1958/1959), 337 – 344 (German). Herbert Grötzsch, Zur Theorie der diskreten Gebilde. IX. Über Heawoodsche Gleichungen und Möglichstgleichverteilung von Signaturen, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg. Math.-Nat. Reihe 8 (1958/1959), 747 – 754 (German).
[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. · Zbl 0832.05084
[17] Hudson V. Kronk, The chromatic number of triangle-free graphs, Graph theory and applications (Proc. Conf., Western Michigan Univ., Kalamazoo, Mich., 1972; dedicated to the memory of J. W. T. Youngs), Springer, Berlin, 1972, pp. 179 – 181. Lecture Notes in Math., Vol. 303. · Zbl 0249.05114
[18] Hudson V. Kronk and Arthur T. White, A 4-color theorem for toroidal graphs, Proc. Amer. Math. Soc. 34 (1972), 83 – 86. · Zbl 0236.05101
[19] B. Mohar and C. Thomassen, Graphs on surfaces, Johns Hopkins University Press, Baltimore (to appear). · Zbl 0979.05002
[20] J. Mycielski, Sur les coloriage des graphs, Colloq. Math. 3 (1955), 161-162. · Zbl 0064.17805
[21] H. Joseph Straight, Cochromatic number and the genus of a graph, J. Graph Theory 3 (1979), no. 1, 43 – 51. · Zbl 0394.05019 · doi:10.1002/jgt.3190030106 · doi.org
[22] H. Joseph Straight, Note on the cochromatic number of several surfaces, J. Graph Theory 4 (1980), no. 1, 115 – 117. · Zbl 0401.05041 · doi:10.1002/jgt.3190040114 · doi.org
[23] Carsten Thomassen, Grötzsch’s 3-color theorem and its counterparts for the torus and the projective plane, J. Combin. Theory Ser. B 62 (1994), no. 2, 268 – 279. · Zbl 0817.05024 · doi:10.1006/jctb.1994.1069 · doi.org
[24] -, Color critical graphs on a fixed surface, to appear. · Zbl 0883.05051
[25] D. A. Youngs, 4-chromatic projective graphs, J. Graph Theory 21 (1996), no. 2, 219 – 227. , https://doi.org/10.1002/(SICI)1097-0118(199602)21:23.0.CO;2-E · Zbl 0839.05040
[26] Michael O. Albertson and Joan P. Hutchinson, The three excluded cases of Dirac’s map-color theorem, Second International Conference on Combinatorial Mathematics (New York, 1978), Ann. New York Acad. Sci., vol. 319, New York Acad. Sci., New York, 1979, pp. 7 – 17. · Zbl 0489.05023
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.