The number of k-colorings of a graph on a fixed surface Original Research Article

We prove that, for every fixed surface S, there exists a largest positive constant c such that every 5-colorable graph with n vertices on S has at least image distinct 5-colorings. This is best possible in the sense that, for each sufficiently large natural number n, there is a graph with n vertices on S that has precisely image distinct 5-colorings. For the sphere the constant c is image, and for each other surface, it is a finite problem to determine c. There is an analogous result for k-colorings for each natural number image.