Claims

../

1992_06_01_alon: Almost every graph on n vertices has list chromatic number at most a constant times n log log n / log n, hence o(n), through the choice number of complete multipartite graphs.

1999_10_01_alon_krivelevich_sudakov: The list chromatic number of the random graph G(n,p) is of order np / log(np) almost surely for 2 < np <= n/2; at p = 1/2 almost every graph has list chromatic number of order n / log n.

---