Five-Coloring Graphs on the Torus

We prove that a graph on the torus is 5-colorable, unless it contains either K6 the complete graph on six vertices, or C3 + C5, the join of two cycles of lengths three and five, respectively, or K2 + H7, the join of K2 and the graph H7 on seven vertices obtained by applying Hajos′ construction to two copies of K4, or a triangulation T11 with 11 vertices of the torus. This answers questions of Albertson, Hutchinson, Stromquist, and Straight.