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.
Original language | English |
---|---|
Journal | Discrete Mathematics |
Volume | 306 |
Issue number | 23 |
Pages (from-to) | 3145-3153 |
ISSN | 0012-365X |
DOIs | |
Publication status | Published - 2006 |
Event | Conference of the European Membrane Society 2006 - Giardini Naxos, Italy Duration: 24 Sept 2006 → 28 Sept 2006 http://euromembrane2006.itm.cnr.it/ |
Conference
Conference | Conference of the European Membrane Society 2006 |
---|---|
Country/Territory | Italy |
City | Giardini Naxos |
Period | 24/09/2006 → 28/09/2006 |
Sponsor | University of Calabria |
Internet address |
Keywords
- Chromatic polynomial
- Graphs on surfaces