Coloring graphs with fixed genus and girth

Abstract:

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\frac {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.