Color-Critical Graphs on a Fixed Surface

Let S be an orientable surface other than the sphere and letkbe a natural number. Then there are infinitely manyk-color-critical graphs onSif and only if 3⩽k⩽5. In particular, ifk⩾5, then there exists a polynomially bounded algorithm for deciding if a graph onScan bek-colored. We extend this to the case where a subgraph of fixed cardinality is precolored. We also establish a corresponding list-color theorem.