The chromatic number of a random graph with o(n 3/2) edges

arXiv:2610.33678 · math.CO, math.PR · Submitted 2026-10-24 · Read on arXiv

math.CO, math.PR

Submitted: 2026-10-24

Updated: 2026-10-24

License: http://creativecommons.org/licenses/by-nc-nd/4.0/

The gist: Let G(n,m) be the Erdos-Renyi random graph with n vertices and m edges and let δ>0.

Abstract

Let G(n,m) be the Erdos-Renyi random graph with n vertices and m edges and let δ>0. Alon and Krivelevich [Combinatorica 1997] proved that for any sequence m at most n 3/2-δ there exists an integer sequence q=q(n) such that the chromatic number of G(n,m) equals either q or q+1 with probability tending to one as n to infinity. In this paper, we give an explicit formula for this sequence q(n) and confirm their result under a less restrictive assumption that m=o(n 3/2). Furthermore, we show that for all but a vanishing proportion of the admissible values of m, the chromatic number of G(n,m) equals q with high probability.

Related papers