List colourings of planar graphs (Q687126)

In an ordinary vertex colouring there is a set of \(k\) colours available, and a vertex colouring picks one of these colours for each vertex so that adjacent vertices receive distinct colours. In a list colouring there is a pre-assigned list of colours at each vertex, and in a colouring a vertex must receive a colour from its list. A graph is \(k\)-choosable if there is a proper list colouring for any assignment of lists with at least \(k\) colours available at each vertex. The choice number of a graph is the smallest \(k\) so that it is \(k\)-choosable. In general, it is possible that a graph's choice number exceeds its chromatic number, in other words, the more general problem may be more difficult. However, the hope is that for special classes of graphs the choice number should be close to the chromatic number. Along these lines, two conjectures of Erdős, Rubin, and Taylor state that (1) there exists a planar graph which is not 4-choosable, and (2) any planar graph is 5- choosable. It is known that there are planar graphs which are not 3- choosable, and that every planar graph is 6-choosable. The author presents a planar graph on 238 vertices which is not 4- choosable, therefore settling Conjecture (1) above. The second conjecture remains open.