Problem Statement
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$?
Does every planar bipartite graph $G$ have $\chi_L(G)\leq 3$?
Categories:
Graph Theory Chromatic Number
Progress
A problem of Erdős, Rubin, and Taylor [ERT80]. The answer is yes, proved by Alon and Tarsi [AlTa92].See also [631].
Source: erdosproblems.com/630 | Last verified: January 15, 2026