The number of k-colorings of a graph on a fixed surface

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 c·2ⁿ 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 c·2ⁿ distinct 5-colorings. For the sphere the constant c is , 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 k>5.