Logo
All Random Solved Random Open
SOLVED
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 bipartite graph $G$ have $\chi_L(G)\leq 3$?

A problem of Erdős, Rubin, and Taylor [ERT80]. The answer is yes, proved by Alon and Tarsi [AlTa92].

See also [631].