Five-coloring graphs on the torus (Q1333321)

Let \(H_ 7\) denote the graph obtained from two disjoint copies of \(K_ 4\) by deleting edge \(xy\) in one of them and edge \(uv\) in the other, adding edge \(yv\), and then identifying vertices \(x\) and \(u\). Let \(T_{11}\) be a particular graph of order 11 (defined precisely in this paper), which triangulates the torus. Let \(G+H\) denote the join of the graphs \(G\) and \(H\). The author proves that a graph imbeddable on the torus can be 5-colored if and only if it contains none of the following: \(K_ 6\), \(C_ 3+C_ 5\), \(K_ 2+H_ 7\), or \(T_{11}\). This result answers several questions posed in the literature. For example, there does exist a polynomially bounded algorithm for deciding if a given graph imbeddable on the torus has a 5-coloring. Moreover, the proof of the above result gives a polynomial time algorithm for actually describing the 5-coloring, if it exists.