List coloring of random and pseudo-random graphs (Q1977428): Difference between revisions

The choice number of a graph \(G\) is the least \(k\) such that whenever a \(k\)-set of colors is assigned to every vertex of \(G\) then there is a good coloring of \(G\) that assigns to each vertex a color from its color set. It is shown that the choice number of the random graph \(G\bigl(n,p(n)\bigr)\) is a.s. \(\Theta \bigl(np(n)/\log\bigl(np(n)\bigr)\bigr)\) if \(2<np(n)\leq n/2\). A bound for the chromatic number of regular graphs is given in terms of the two largest eigenvalues. Finally, it is conjectured that if \(np(n)\to\infty\) then the choice number and the chromatic number of \(G\bigl(n,p(n)\bigr)\) are asymptotically equal.