{"id":"arxiv/2610.33678","url":"https://arxiv.org/abs/2610.33678","tags":["math.CO","math.PR"],"score":0,"title":"The chromatic number of a random graph with $o(n^{3/2})$ edges","domain":"math.CO","source":"arxiv","authors":["Amin Coja-Oghlan","Mikhail Isaev","Mihyun Kang","Pavel Zakharov"],"reviews":0,"subject":"math.CO","summary":"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\\leq n^{3/2-δ}$ there \\emph{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\\infty$. 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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-24","reactions":{}}