Coloring graphs without short non-bounding cycles (Q1322020)

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 [\textit{R. J. Cook}, Chromatic number and girth, Period. Math. Hungar. 6, 103-107 (1975; Zbl 0313.05107)], Woodburn [\textit{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.