List coloring

Remarks

If all lists equal $\set{1, \dots, k}$, an $L$-colouring is a proper colouring with $k$ colours, so $\operatorname{ch}(G) \ge \chi(G)$, where $\chi$ is the chromatic number. Example: every tree is $2$-choosable. Colour the vertices in an order in which each vertex after the first has exactly one earlier neighbour. Each vertex then picks a colour of its list other than the colour of that neighbour. Non-example: $K_{3,3}$ is not $2$-choosable, although $\chi(K_{3,3}) = 2$. Give the vertices on each side the lists $\set{1,2}$, $\set{1,3}$ and $\set{2,3}$. The colours used on one side meet each of these three sets, so they include at least two colours. Two of these colours form the list of some vertex on the other side, and that vertex fails clause 2. Thomassen proved that every planar graph is $5$-choosable. Choice number is also called list chromatic number and written $\chi_\ell(G)$.