The Choice Number of Random Graphs

In 1999, Alon, Krivelevich and Sudakov conjectured that the choice number and chromatic number of the random graph $G(n,p)$ are asymptotically equal whenever np→∞. We prove their conjecture, showing that, with high probability, ch(G(n,p))=(1+o(1))χ(G(n,p)) whenever np→∞. This improves the bound ch(G(n,p))≤(2+o(1))χ(G(n,p)) for np→∞ and p≤0.9 obtained by Krivelevich and Vu in 2001. Our proof distinguishes two cases according to the size of independent sets. When independent sets of growing size are available, we establish a sharper uniform independent-set estimate that eliminates the factor-two loss in the bound of Krivelevich and Vu. When independent sets have bounded size, we establish a deterministic result showing that, under a suitable uniform independent-set condition, a proper colouring with bounded colour-class sizes yields an asymptotically matching upper bound on the choice number.