Journal article ยท Conference paper
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 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.
Language: | English |
---|---|
Year: | 2006 |
Pages: | 3145-3153 |
Proceedings: | Conference of the European Membrane Society 2006 |
ISSN: | 1872681x and 0012365x |
Types: | Journal article and Conference paper |
DOI: | 10.1016/j.disc.2005.04.027 |
ORCIDs: | Thomassen, Carsten |