Coloring graphs with fixed genus and girth

It is well known that the maximum chromatic number of a graph on the orientable surface S-g is theta(g(1/2)). We prove that there are positive 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 girth on S-g or N-k. As an application, we prove that an S-g-polytope has chromatic number at most O(g(3/7)). For specific surfaces we prove that every graph on the double torus and of girth at least six is 3-colorable and we characterize completely those triangle-free projective graphs that are not 3-colorable.