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

Carsten Thomassen

doi:10.1016/j.disc.2005.04.027

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

Research output: Contribution to journal › Conference article › Research › peer-review

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	https://doi.org/10.1016/j.disc.2005.04.027
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	http://euromembrane2006.itm.cnr.it/

Keywords

Chromatic polynomial
Graphs on surfaces

Access to Document

10.1016/j.disc.2005.04.027

OpenUrl availability

Full text

Cite this

@inproceedings{8d4ac75921284d02bc08e5f1b36376f7,

title = "The number of k-colorings of a graph on a fixed surface",

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. ",

keywords = "Chromatic polynomial, Graphs on surfaces",

author = "Carsten Thomassen",

year = "2006",

doi = "10.1016/j.disc.2005.04.027",

language = "English",

volume = "306",

pages = "3145--3153",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier",

number = "23",

note = "Conference of the European Membrane Society 2006, EUROMEMBRANE 2006 ; Conference date: 24-09-2006 Through 28-09-2006",

url = "http://euromembrane2006.itm.cnr.it/",

}

TY - GEN

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

AU - Thomassen, Carsten

PY - 2006

Y1 - 2006

N2 - 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.

AB - 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.

KW - Chromatic polynomial

KW - Graphs on surfaces

U2 - 10.1016/j.disc.2005.04.027

DO - 10.1016/j.disc.2005.04.027

M3 - Conference article

SN - 0012-365X

VL - 306

SP - 3145

EP - 3153

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 23

T2 - Conference of the European Membrane Society 2006

Y2 - 24 September 2006 through 28 September 2006

ER -

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

Abstract

Conference

Keywords

Access to Document

OpenUrl availability

Fingerprint

Cite this