List coloring of random and pseudo-random graphs

The choice number of a graph G is the minimum integer k such that for every assignment of a set S(v) of k colors to every vertex v of G, there is a proper coloring of G that assigns to each vertex v a color from S(v). It is shown that the choice number of the random graph G(n,p(n)) is almost surely θ ( np(n)/ln(np(n)) whenever 2 < np(n) ≤ n/2. A related result for pseudo-random graphs is proved as well. By a special case of this result, the choice number (as well as the chromatic number) of any graph on n vertices with minimum degree at least n/2 - n^0.99 in which no two distinct vertices have more than n/44+n^0.99 common neighbors is at most O(n/lnn).