zbMATH — the first resource for mathematics

Coloring graphs without short non-bounding cycles. (English) Zbl 0793.05058
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.

MSC:
 05C15 Coloring of graphs and hypergraphs 05C38 Paths and cycles 05C10 Planar graphs; geometric and topological aspects of graph theory
Full Text: