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 pr oper coloring of G that assigns to each vertex v a color from S(v). It is s hown that the choice number of the random graph G(n,p(n)) is almost surely -(np(n)/ln(np(n))) whenever 2 < np(n) less than or equal to n/2. A related result for pseudo-random graphs is proved as well. By a special case of thi s 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 di stinct vertices have more than n/4 + n(0.99) common neighbors is at most O( n/ln n).