Exponentially many 5-list-colorings of planar graphs

Carsten Thomassen

doi:10.1016/j.jctb.2006.09.002

Exponentially many 5-list-colorings of planar graphs

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

Abstract

We prove that every planar graph with n vertices has at least 2n/9 distinct list-colorings provided every vertex has at least five available colors.

Original language	English
Journal	Journal of Combinatorial Theory. Series B
Volume	97
Issue number	4
Pages (from-to)	571-583
ISSN	0095-8956
DOIs	https://doi.org/10.1016/j.jctb.2006.09.002
Publication status	Published - 2007

Keywords

List colorings

Access to Document

10.1016/j.jctb.2006.09.002

OpenUrl availability

Full text

Cite this

@article{a896ab4f26424218a8c6503eafd572e8,

title = "Exponentially many 5-list-colorings of planar graphs",

abstract = "We prove that every planar graph with n vertices has at least 2n/9 distinct list-colorings provided every vertex has at least five available colors.",

keywords = "List colorings",

author = "Carsten Thomassen",

year = "2007",

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

language = "English",

volume = "97",

pages = "571--583",

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

issn = "0095-8956",

publisher = "Academic Press",

number = "4",

}

TY - JOUR

T1 - Exponentially many 5-list-colorings of planar graphs

AU - Thomassen, Carsten

PY - 2007

Y1 - 2007

N2 - We prove that every planar graph with n vertices has at least 2n/9 distinct list-colorings provided every vertex has at least five available colors.

AB - We prove that every planar graph with n vertices has at least 2n/9 distinct list-colorings provided every vertex has at least five available colors.

KW - List colorings

U2 - 10.1016/j.jctb.2006.09.002

DO - 10.1016/j.jctb.2006.09.002

M3 - Journal article

SN - 0095-8956

VL - 97

SP - 571

EP - 583

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

IS - 4

ER -

Exponentially many 5-list-colorings of planar graphs

Abstract

Keywords

Access to Document

OpenUrl availability

Fingerprint

Cite this