The chromatic polynomial and list colorings

Carsten Thomassen

doi:10.1016/j.jctb.2008.09.005

The chromatic polynomial and list colorings

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

Abstract

We prove that, if a graph has a list of k available colors at every vertex, then the number of list-colorings is at least the chromatic polynomial evaluated at k when k is sufficiently large compared to the number of vertices of the graph.

Original language	English
Journal	Journal of Combinatorial Theory. Series B
Volume	99
Issue number	2
Pages (from-to)	474-479
ISSN	0095-8956
DOIs	https://doi.org/10.1016/j.jctb.2008.09.005
Publication status	Published - 2009

Keywords

List coloring
Chromatic polynomial

Access to Document

10.1016/j.jctb.2008.09.005

OpenUrl availability

Full text

Cite this

@article{7ab82c46735e4e31968b9dd598f32a88,

title = "The chromatic polynomial and list colorings",

abstract = "We prove that, if a graph has a list of k available colors at every vertex, then the number of list-colorings is at least the chromatic polynomial evaluated at k when k is sufficiently large compared to the number of vertices of the graph.",

keywords = "List coloring, Chromatic polynomial",

author = "Carsten Thomassen",

year = "2009",

doi = "10.1016/j.jctb.2008.09.005",

language = "English",

volume = "99",

pages = "474--479",

journal = "Journal of Combinatorial Theory. Series B",

issn = "0095-8956",

publisher = "Academic Press",

number = "2",

}

TY - JOUR

T1 - The chromatic polynomial and list colorings

AU - Thomassen, Carsten

PY - 2009

Y1 - 2009

N2 - We prove that, if a graph has a list of k available colors at every vertex, then the number of list-colorings is at least the chromatic polynomial evaluated at k when k is sufficiently large compared to the number of vertices of the graph.

AB - We prove that, if a graph has a list of k available colors at every vertex, then the number of list-colorings is at least the chromatic polynomial evaluated at k when k is sufficiently large compared to the number of vertices of the graph.

KW - List coloring

KW - Chromatic polynomial

U2 - 10.1016/j.jctb.2008.09.005

DO - 10.1016/j.jctb.2008.09.005

M3 - Journal article

SN - 0095-8956

VL - 99

SP - 474

EP - 479

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

IS - 2

ER -

The chromatic polynomial and list colorings

Abstract

Keywords

Access to Document

OpenUrl availability

Fingerprint

Cite this