Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4651350 | Discrete Mathematics | 2006 | 4 Pages |
Abstract
A graph G=G(V,E)G=G(V,E) is called L-list colourable if there is a vertex colouring of G in which the colour assigned to a vertex vv is chosen from a list L(v)L(v) associated with this vertex. We say G is kk-choosable if all lists L(v)L(v) have the cardinality k and G is L-list colourable for all possible assignments of such lists. There are two classical conjectures from Erdős, Rubin and Taylor 1979 about the choosability of planar graphs:(1)every planar graph is 5-choosable and,(2)there are planar graphs which are not 4-choosable.We will prove the second conjecture.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Margit Voigt,