The Choice Number of Random Graphs
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→∞. 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.
Related
- Planarity and number of crossings in general models of random geometric graphs
- Sharp asymptotics for the Lovász number of random circulant graphs
- On the Stability of the Independence Number in Random Distance Graphs
- Exponential tails for factors and the chromatic number of random graphs
- The strong fractional choice number can exceed the choice number
BibTeX
@misc{wang2026choice,
title = {{The Choice Number of Random Graphs}},
author = {Lanchao Wang and Jiasheng Zeng},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.35003},
eprint = {2610.35003},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.35003},
}
RIS
TY - UNPB
TI - The Choice Number of Random Graphs
AU - Lanchao Wang
AU - Jiasheng Zeng
PY - 2026
DA - 2026/10/26
PB - arXiv
DO - 10.48550/arxiv.2610.35003
UR - https://arxiv.org/abs/2610.35003
AB - 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.
ER -