Status
On this page
Status
Topics
Status
On this page
Status
Topics
The list chromatic number is defined to be the minimal such that for any assignment of a list of colours to each vertex of (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 have ?
Source: erdosproblems.com/630
An accepted solution exists. The statement is true.
Proved on the site (label PROVED). The site attributes the question to Erdős, Rubin and Taylor [ERT80], credits Alon and Tarsi [AlTa92] with the answer yes, and points to Problem 631. The community database (teorth/erdosproblems) lists the problem as proved with a Lean proof from 2026-09-16, the date of the formalization recorded under Formalization. The standing rests on Alon and Tarsi's theorem, accepted on its refereed publication and the curator's credit: a planar bipartite graph has an orientation of maximum outdegree at most in which every Eulerian subgraph has an even number of edges, and their algebraic criterion then colors it from any lists of size .