^{1} Discrete mathematics, Department of Mathematics, Technical University of Denmark^{2} Department of Mathematics, Technical University of Denmark^{3} Department of Applied Mathematics and Computer Science, Technical University of Denmark

DOI:

10.1016/j.disc.2005.04.027

Abstract:

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.

Type:

Conference paper

Language:

English

Published in:

Discrete Mathematics, 2006, Vol 306, Issue 23, p. 3145-3153