Determine n(k): the fewest vertices in a bipartite graph with list chromatic number exceeding k (Erdős #629)
Statement
The list chromatic number $\chi_L(G)$ is 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$.
Acceptance. FULLY RESOLVES: an exact formula for $n(k)$, or a determination of its asymptotics precise enough to close the gap between the lower and upper bounds stated in the background, with complete proof (machine-checkable Lean/Coq preferred, else a full written proof). ADVANCES: the exact value of $n(4)$ — deliver an explicit bipartite graph $G$ on $n(4)$ vertices together with a machine-checkable certificate that $\chi_L(G)>4$ (a list assignment of 4-lists plus refutation certificates for all colourings, or an equivalent verified computation), and an exhaustiveness certificate (search code plus logs/proof) that every bipartite graph on fewer vertices has $\chi_L\leq 4$; or any new exact value $n(k)$ for $k\geq 4$ by the same standard; or asymptotic upper or lower bounds on $n(k)$ strictly improving the best bounds stated in the background, with proof; or an improved recursion strictly sharpening [HMT96]. Deliver the proof file, or the extremal graph plus verification code, certificates, and the exhaustive-search artifact.
Background
Posed by Erdős, Rubin, and Taylor in their foundational list-colouring paper [ERT80]; listed as open on erdosproblems.com/629 (fetched 2026-07-13, status 'open', tagged 'graph theory | chromatic number'). [ERT80] proved $2^{k-1}<n(k)<k^2 2^{k+2}$ and computed $n(2)=6$; Hanson, MacGillivray, and Toft [HMT96] proved $n(3)=14$ and the recursion $n(k)\leq k\,n(k-2)+2^k$. The problem is sandwich-coupled to property B: if $m(k)$ is the minimum number of sets in a $k$-uniform set family that is not 2-colourable, then $m(k)\leq n(k)\leq m(k+1)$ [ERT80], and the Radhakrishnan–Srinivasan lower bound on $m(k)$ [RaSr00] gives $n(k)\gg 2^k (k/\log k)^{1/2}$. The first unknown value is $n(4)$: since $m(4)=23$ (Östergård, 2014) the sandwich gives $n(4)\geq 23$, while the [HMT96] recursion gives $n(4)\leq 4\,n(2)+2^4=40$. Note the venue already hosts the closely related problem of determining $m(5)$ (fewest edges in a non-2-colourable 5-uniform hypergraph, Erdős #901, erdosproblems.com/901), which is exactly the upper member of the sandwich for $n(4)$ — this problem is distinct (bipartite list colouring) but progress can flow both ways. Also catalogued in the UCSD Erdős graph-problems collection. The attacker's tool: determining $n(4)$ is a finite combinatorial search over bipartite graphs on 23–40 vertices, amenable to SAT/CP encodings of list-colourability (quantify over list assignments, refute all choice functions) with symmetry breaking; the asymptotics need probabilistic and hypergraph-colouring arguments.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #629 (T. F. Bloom) | website |
| REF-02 | UCSD Erdős graph problems: list colouring bipartite graphs | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.