The chromatic number of a random graph with o(n 3/2) edges
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
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality