Fisk, Steve; Mohar, Bojan Coloring graphs without short non-bounding cycles. (English) Zbl 0793.05058 J. Comb. Theory, Ser. B 60, No. 2, 268-276 (1994). It is shown that there is a constant \(c\) such that if \(G\) is a graph embedded in a surface of genus \(g\) (either orientable or non-orientable) and the length of a shortest non-bounding cycle of \(G\) is at least \(c\log(g+1)\), then \(G\) is 6-colorable. The same condition together with the additional assumption that the girth of \(G\) is at least 4 (respectively, 6) guarantees that \(G\) can be 4-colored (respectively, 3- colored). The fact that the proofs use nothing but elementary techniques sheds some new light on the problem of coloring graphs on surfaces. These results improve and generalize results obtained by Cook [R. J. Cook, Chromatic number and girth, Period. Math. Hungar. 6, 103-107 (1975; Zbl 0313.05107)], Woodburn [R. L. Woodburn, A 4-color theorem for the Klein bottle, Discrete Math. 76, No. 3, 271-276 (1989; Zbl 0685.05019)], and some other people. The results also complement a recent outcome of Thomassen who proved a five color theorem of the same type under stronger hypotheses. Reviewer: B.Mohar (Ljubljana) Cited in 16 Documents MSC: 05C15 Coloring of graphs and hypergraphs 05C38 Paths and cycles 05C10 Planar graphs; geometric and topological aspects of graph theory Keywords:chromatic number; locally planar graphs; map coloring; cycle; coloring graphs; surfaces Citations:Zbl 0313.05107; Zbl 0685.05019 PDFBibTeX XMLCite \textit{S. Fisk} and \textit{B. Mohar}, J. Comb. Theory, Ser. B 60, No. 2, 268--276 (1994; Zbl 0793.05058) Full Text: DOI