Color-critical graphs on a fixed surface (Q1369650)

A graph is \(k\)-color-critical if its vertex chromatic number is \(k\), but every proper subgraph is (\(k-1\))-colorable. It is known that for each orientable surface \(S\) and for each \(k \geq 7\), there are only finitely many \(k\)-color-critical graphs on \(S\). On the other hand, there are infinitely many 5-critical graphs on each surface \(S\) except the sphere. In this paper the author shows that for each orientable surface \(S\) there are only finitely many 6-color-critical graphs on \(S\). He also shows that if \(k \geq 5\), then there exists a polynomially-bounded algorithm for deciding if a graph on \(S\) can be \(k\)-colored. The techniques involve cutting the surface and graph to transform it into a planar graph, then applying various 5-coloring results for planar graphs. Some extensions of the results are given where a small subgraph is pre-colored, to list colorings, and to non-orientable surfaces.