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.
Is it true that $\chi_L(G)=o(n)$ for almost all graphs on $n$ vertices?
Is it true that $\chi_L(G)=o(n)$ for almost all graphs on $n$ vertices?
Categories:
Graph Theory Chromatic Number
Progress
A problem of Erdős, Rubin and Taylor.The answer is yes: Alon [Al92] proved that in fact the random graph on $n$ vertices with edge probability $1/2$ has\[\chi_L(G) \ll \frac{\log\log n}{\log n}n\]almost surely. Alon, Krivelevich, and Sudakov [AKS99] improved this to\[\chi_L(G) \asymp \frac{n}{\log n}\]almost surely.
Source: erdosproblems.com/799 | Last verified: January 16, 2026