List coloring of random and pseudo-random graphs

Noga Alon, Michael Krivelevich, Benny Sudakov

Research output: Contribution to journalArticlepeer-review

25 Scopus citations


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/44+n0.99 common neighbors is at most O(n/lnn).

Original languageEnglish (US)
Pages (from-to)453-472
Number of pages20
Issue number4
StatePublished - 1999
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics


Dive into the research topics of 'List coloring of random and pseudo-random graphs'. Together they form a unique fingerprint.

Cite this