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 n0:99 in which no two distinct vertices have more than n=4 +n0:99 common neighbors is at most O(n= lnn).