Logo
All Random Solved Random Open
OPEN
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$.

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 with property B (i.e. there is a set which intersects each member of the member yet does not contain any of them) then $m(k)\leq n(k)\leq m(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.