COLORING GRAPHS WITH FIXED GENUS AND GIRTH

It is well known that the maximum chromatic number of a graph on the o rientable surface S-g is theta(g(1/2)). We prove that there are positi ve 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)g(1/3)/log(g). We obtain similar results for graphs with restricted clique number or gi rth on S-g or N-k. As an application, we prove that an S-g-polytope ha s chromatic number at most O(g(3/7)). For specific surfaces we prove t hat every graph on the double torus and of girth at least six is 3-col orable and we characterize completely those triangle-free projective g raphs that are not 3-colorable.