Abstract
It is well known that the maximum chromatic number of a graph on the orientable surface S g S_g is θ ( g 1 / 2 ) \theta (g^{1/2}) . We prove that there are positive constants c 1 , c 2 c_1,c_2 such that every triangle-free graph on S g S_g has chromatic number less than c 2 ( g / log ⁡ ( g ) ) 1 / 3 c_2(g/\log (g))^{1/3} and that some triangle-free graph on S g S_g has chromatic number at least c 1 g 1 / 3 log ⁡ ( g ) c_1\frac {g^{1/3}}{\log (g)} . We obtain similar results for graphs with restricted clique number or girth on S g S_g or N k N_k . As an application, we prove that an S g S_g -polytope has chromatic number at most O ( g 3 / 7 ) 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.

This publication has 15 references indexed in Scilit: