All Random Solved Random Open
The list chromatic number $\chi_L(G)$ is defined to be the minimal $k$ such that for any assignment of a list of $k$ colours to each vertex of $G$ (perhaps different lists for different vertices) a colouring of each vertex by a colour on its list can be chosen such that adjacent vertices receive distinct colours.

Does every planar graph $G$ have $\chi_L(G)\leq 5$? Is this best possible?

A problem of Erdős, Rubin, and Taylor [ERT80]. The answer to both is yes: Thomassen [Th94] proved that $\chi_L(G)\leq 5$ if $G$ is planar, and Voigt [Vo93] constructed a planar graph with $\chi_L(G)=5$. A simpler construction was given by Gutner [Gu96].

See also [630].