Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated Oct 8

Problem 1156

claims/: The 2 claim pages of Problem 1156, one per claimant's result; the problem's standing derives from them.

Statement. 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?

Formulation. The standing answers the site's wording, the only Statement shown. Its first question asks for concentration on at most $C$ values, not necessarily consecutive. So worded it is open: the site's discussion thread (26 January 2026) records that concentration of $\chi(G)$ on two far-apart values has not been excluded. Erdős's question in the appendix to Alon and Spencer's The Probabilistic Method (1992), as Heckel [He21] quotes it, asks instead whether $\chi(G)$ can be shown not to be concentrated on a series of intervals of constant length, that is, on $C$ consecutive values. That version has the answer no, as the Current assessment records. The second question asks for non-concentration at every large $n$ and is open under either reading.

Status. Open.

Source. erdosproblems.com/1156, accessed 2026-09-04. Cite as: T. F. Bloom, Erdős Problem #1156, https://www.erdosproblems.com/1156.

References.

[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.

Formalization. None recorded.

Current assessment

The standing judges the site's formulation, accessed and read as the Formulation states. Both of its questions are open. The known upper bounds are these. Bollobás [Bo88] proved that $\chi(G)\sim n/(2\log_2 n)$ with high probability. Shamir and Spencer [ShSp87] proved that $\chi(G)$ lies with high probability in an interval of length $\omega(n)\sqrt n$ about some $f(n)$ , for any $\omega(n)\to\infty$ . Alon improved the length to $\omega(n)\sqrt n/\log n$ , posed as Exercise 3 of Section 7.9 of Alon and Spencer [AlSp16]; Scott [Sc17] gives a proof (Scott 2008).

Two refereed results bound the concentration from below and answer the consecutive-values version of the first question, Erdős's question of 1992, with no. Heckel [He21] proved that for no constant $c<1/4$ does a sequence of intervals of length $n^c$ contain $\chi(G)$ with high probability; this is the accepted partial claim on its claim page. Heckel and Riordan [HeRi23] raised the exponent to every $c<1/2$ , for every fixed edge probability $p\in(0,1)$ , the accepted partial claim on its claim page. In particular $\chi(G)$ is not concentrated on one value. Neither result settles a question as the site words it. Concentration on two far-apart values is not excluded, and since both results give long intervals only for infinitely many $n$ , concentration on one value for almost all $n$ is not excluded either, so the second question stays open.

Search scope: the site's problem page (last edited 27 January 2026), its discussion thread and proof-claims tab (no proof claim), the community database (no formalized statement), formal-conjectures (no file for Problem 1156) and arXiv, accessed 2026-10-07.

Linked library material

These entries are derived from explicit links on library pages. They are navigation only and do not by themselves record mathematical progress.

Linked from (17)

Heckel's non-concentration of the chromatic number of G(n,1/2)Heckel and Riordan's square-root non-concentration of the chromatic number problems/graph_coloring/E1156/claims Graph Coloring Non-concentration of the chromatic number of a random graph Conjecture and open questions (p. 12): intervals of length n^(1/2-eps), a lower bound for every large n, and the correct exponent Corollary (p. 12): the conclusion of Theorem 3 holds for the uniform random graph G(n,m) with m = floor(n^2/4)Theorem 3 (p. 2): for no constant c < 1/4 do intervals of length n^c contain the chromatic number of G(n,1/2) with high probability graph_coloring/heckel_2023_how_does_chromatic_number_random_graph Conjecture 10 (p. 8): the Zigzag Conjecture, concentration width n^{lambda+o(1)} with lambda = max(theta/2, (1-theta)/2)Corollary 39 (p. 29): partial derivatives of L_0(n,k,t), the approximation to the log of the expected number of t-bounded k-colourings of G_{n,1/2}Theorem 5 (p. 3): intervals holding chi(G_{n,p}) whp are longer than n^c for infinitely many n, for every c < 1/2 Theorem 6 (p. 4): near each n with mu_alpha(n) < n^{1-eps} some n* = (1+o(1))n has an interval longer than C sqrt(mu_alpha(n*))/log n*Theorem 8 (p. 5): conditional on (7), intervals holding chi(G_{n,1/2}) with probability 0.9 have length at least c sqrt(n*) log log n* / log^3 n* along a sequence n*graph_coloring/scott_2008_concentration_chromatic_number_random_graphs Lemma 2 (pp. 2-3): for fixed p, with probability 1 - o(1) every vertex set of G(n,p) of more than n^{1/3} vertices contains a clique of at least c(p) log n vertices Theorem 1 (p. 2): for fixed p the chromatic number of G(n,p) lies within omega(n) sqrt(n)/log n of some h(n) with probability 1 - o(1)

Graph