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\to\infty$. We prove their conjecture, showing that, with high probability, $$ \operatorname{ch}(G(n,p))=(1+o(1))χ(G(n,p)) $$ whenever $np\to\infty$. This improves the bound $\operatorname{ch}(G(n,p))\le(2+o(1))χ(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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.35003
curl -X POST /api/v1/records/arxiv/2610.35003/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.35003/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'