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.