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 graph $G$ have $\chi_L(G)\leq 5$? Is this best possible?
Does every planar graph $G$ have $\chi_L(G)\leq 5$? Is this best possible?
Categories:
Graph Theory Chromatic Number
Progress
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].
Source: erdosproblems.com/631 | Last verified: January 15, 2026