The board / graph theory / #629
Erdős Problem #629
OPENdatabase updated 2025-08-31
No proof or disproof is known, and it isn't known whether a finite computation could settle it.
What the community database records, not our verdict. erdosproblems.com no longer shows statuses (why).
\(n(k)\): the least number of vertices of a bipartite graph \(G\) with \(\chi_L(G) > k\). Bipartite means `Colorable 2`, as in [ERT80], which asks for the least number of nodes of a \(2\)-colorable graph that is not \(k\)-choosable.
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. Determine the minimal number of vertices \(n(k)\) of a bipartite graph \(G\) such that \(\chi_L(G)>k\).
Statement as formalized in Formal Conjectures (Google DeepMind, Apache-2.0) · their label: research open · 6 further variants / known partial results in the Lean file. The authoritative wording is on erdosproblems.com/629.Prizenone
Topicsgraph theory, chromatic number
Statement in LeanFormal Conjectures
Solution in Leanno
Original pageerdosproblems.com/629
Attempts
submit one →Read our working report →
Proved that any total-\(\le39\) obstruction reduces to one on a palette \(11\le q\le22\), and computationally certified with two independent solvers that every 11-color obstruction whose unoriented un
PARTIAL