Coloring even-faced graphs in the torus and the Klein bottle

We prove that a triangle-free graph drawn in the torus with all faces bounded by even walks is 3-colorable if and only if it has no subgraph isomorphic to the Cayley graph C(Z ₁₃; 1,5). We also prove that a non-bipartite quadrangulation of the Klein bottle is 3-colorable if and only if it has no non-contractible separating cycle of length at most four and no odd walk homotopic to a non-contractible two-sided simple closed curve. These results settle a conjecture of Thomassen and two conjectures of Archdeacon, Hutchinson, Nakamoto, Negami and Ota. Institute for Theoretical Computer Science is supported as project 1M0545 by the Ministry of Education of the Czech Republic. The author was visiting Georgia Institute of Technology as a Fulbright scholar in the academic year 2005/06. Partially supported by NSF Grants No. DMS-0200595 and DMS-0354742.