LIST COLORINGS OF PLANAR GRAPHS

A graph G = G(V, E) is called L-list colourable if there is a vertex c olouring of G in which the colour assigned to a vertex v is chosen fro m a list L(v) associated with this vertex. We say G is k-choosable if all fists L(v) have the cardinality k and G is L-list colourable for a ll possible assignments of such lists. There are two classical conject ures from Erdos, Rubin and Taylor 1979 about the choosability of plana r graphs: (1) every planar graph is 5-choosable and, (2) there are pla nar graphs which are not 4-choosable. We will prove the second conject ure.