Problem 1156

Let $G$ be a random graph on $n$ vertices, in which every edge is included independently with probability $1/2$ .

Is there some constant $C$ such that that chromatic number $\chi(G)$ is, almost surely, concentrated on at most $C$ values?

Is it true that, if $\omega(n)\to \infty$ sufficiently slowly, then for every function $f(n)$

\mathbb{P}(\lvert\chi(G)-f(n)\rvert<\omega(n))<1/2

if $n$ is sufficiently large?

Status

Open

No claim settles this problem.

AlSp16: Alon, Noga and Spencer, Joel H., The probabilistic method. (2016), xiv+375.
Bo88: Bollobás, B., The chromatic number of random graphs. Combinatorica (1988), 49-55.
He21: Heckel, Annika, Non-concentration of the chromatic number of a random graph. J. Amer. Math. Soc. (2021), 245-260.
HeRi23: Heckel, Annika and Riordan, Oliver, How does the chromatic number of a random graph vary?. J. Lond. Math. Soc. (2) (2023), 1769-1815.
Sc17: A. Scott, On the concentration of the chromatic number of random graphs. arXiv:0806.0178 (2017).
ShSp87: Shamir, E. and Spencer, J., Sharp concentration of the chromatic number on random graphs $G_{n,p}$ . Combinatorica (1987), 121-129.