Skip to content
Preprint

The Choice Number of Random Graphs

Oct 2026 · 0 citations · 18 references
Mathematics

Abstract

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\to\infty$. We prove their conjecture, showing that, with high probability, $$ \operatorname{ch}(G(n,p))=(1+o(1))\chi(G(n,p)) $$ whenever $np\to\infty$. This improves the bound $\operatorname{ch}(G(n,p))\le(2+o(1))\chi(G(n,p))$ for $np\to\infty$ and $p\le0.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.

View source

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.