1 Discrete mathematics, Department of Mathematics, Technical University of Denmark2 Department of Mathematics, Technical University of Denmark3 Department of Applied Mathematics and Computer Science, Technical University of Denmark
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 center dot 2(n) 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 center dot 2(n) distinct 5-colorings. For the sphere the constant c is 15/2, 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. (c) 2006 Elsevier B.V. All rights reserved.
Discrete Mathematics, 2006, Vol 306, Issue 23, p. 3145-3153