C. Thomassen, Color-critical graphs on a fixed surface, MAT-REPORT NO. 1994-44, The Technical University of Denmark, November 1994, 37 pages.
Abstract:
Let S be an orientable surface other than the sphere and let k
be a natural number. Then there are infinitely many k-color-
critical graphs on S if and only if 3<=k<=5. In particular,
if k>=5, then there exists a polynomially bounded algorithm
for deciding if a graph on S can be k-colored. We extend
this to the case where a subgraph of fixed cardinality is
precolored. We also establish a corresponding list-color theorem.
Bjarne Toft, March 15, 1995.
C. Thomassen, Color-Critical Graphs on a Fixed Surface, Journal Comb. Theory B 70 (1997), 67-100.
Bjarne Toft, August 6, 1997.