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.
Determine the minimal number of vertices $n(k)$ of a bipartite graph $G$ such that $\chi_L(G)>k$.
Determine the minimal number of vertices $n(k)$ of a bipartite graph $G$ such that $\chi_L(G)>k$.
Categories:
Graph Theory Chromatic Number
Progress
A problem of Erdős, Rubin, and Taylor [ERT80], who proved that\[2^{k-1}<n(k) <k^22^{k+2}.\]They also prove that if $m(k)$ is the size of the smallest family of $k$-sets without property B (i.e. the smallest number of $k$-sets in a graph with chromatic number $3$) then $m(k)\leq n(k)\leq m(k+1)$. Bounds on $m(k)$ are the subject of [901]. The lower bounds on $m(k)$ by Radhakrishnan and Srinivasan [RaSr00] imply that\[2^k \left(\frac{k}{\log k}\right)^{1/2}\ll n(k).\]Erdős, Rubin, and Taylor [ERT80] proved $n(2)=6$ and Hanson, MacGillivray, and Toft [HMT96] proved $n(3)=14$ and\[n(k) \leq kn(k-2)+2^k.\]See also the entry in the graphs problem collection.Source: erdosproblems.com/629 | Last verified: January 15, 2026