PreprintCC BY-NC-ND 4.0arXiv
The chromatic number of a random graph with o(n3/2) edges
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≤ n3/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→∞. 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(n3/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
- On the limiting distribution of the number of improper edges for random trees
- A planar signed graph with circular chromatic number five
- Adjacent vertex distinguishing total chromatic number of graph products
- Local Antimagic Chromatic Number of Middle Graph and Direct Product of Graphs
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
BibTeX
@misc{cojaoghlan2026chromatic,
title = {{The chromatic number of a random graph with $o(n^3/2)$ edges}},
author = {Amin Coja-Oghlan and Mikhail Isaev and Mihyun Kang and Pavel Zakharov},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.33678},
eprint = {2610.33678},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.33678},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - The chromatic number of a random graph with o(n^3/2) edges
AU - Amin Coja-Oghlan
AU - Mikhail Isaev
AU - Mihyun Kang
AU - Pavel Zakharov
PY - 2026
DA - 2026/10/24
PB - arXiv
DO - 10.48550/arxiv.2610.33678
UR - https://arxiv.org/abs/2610.33678
AB - 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≤ 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→∞. 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.
ER -