Choosability of planar graphs

A graph G = G( V, E) with lists L( v), associated with its vertices v ∈ V, is called L-list colourable if there is a proper vertex colouring of G in which the colour assigned to a vertex v is chosen from L( v). We say G is k- choosable if there is at least one L-list colouring for every possible list assignment L with ∥ L( v)∥ = k ∀ v ∈ V( G). Now, let an arbitrary vertex v of G be coloured with an arbitrary colour f of L( v). We investigate whether the colouring of v can be continued to an L-list colouring of the whole graph. G is called free k-choosable if such an L-list colouring exists for every list assignment L (∥ L( v)∥ = k ∀ v ∈ V( G)), every vertex v and every colour f ∈ L( v). We prove the equivalence of the well-known conjecture of Erdős et al. (1979): “Every planar graph is 5-choosable” with the following conjecture: “Every planar graph is free 5-choosable”.

VIVO