×

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
PDFBibTeX XMLCite
Full Text: DOI