Article ID Journal Published Year Pages File Type
4651350 Discrete Mathematics 2006 4 Pages PDF
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
,