Problem 920

Let $f_k(n)$ be the maximum possible chromatic number of a graph with $n$ vertices which contains no $K_k$ .

Is it true that, for $k\geq 4$ ,

f_k(n) \gg \frac{n^{1-\frac{1}{k-1}}}{(\log n)^{c_k}}

for some constant $c_k>0$ ?

Source: erdosproblems.com/920

Graph theory
Chromatic number

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

SOLVED, the site's label (page last edited 25 July 2026); the site credits the case $k=4$ to Mattheus and Verstraete's bound on $r(4,t)$ and the cases $k\ge5$ to Bradač's off-diagonal Ramsey bound, and the claim pages Mattheus–Verstraete 2023 and Bradač 2026 record the two results, each accepted for its range. The two parts of the question, $k=4$ and $k\ge5$ , are each settled by an accepted partial claim. The derived standing is proved, where the site's label records only that the problem is answered, because the question asks whether the bound holds and both claims prove that it does: the answer is yes for every $k\ge4$ .

Br26: Bradač, D., Off-diagonal Ramsey numbers. arXiv:2605.28793 (2026); the first version, of 27 May 2026, carried the title "Nearly tight exponents for off-diagonal Ramsey numbers", which the site's reference uses; the third version, of 16 June 2026, is the version cited.
GrYa68: Graver, Jack E. and Yackel, James, Some graph theoretic results associated with Ramsey's theorem. J. Combinatorial Theory 4 (1968), 125--175; the Corollary to Proposition 9, printed p. 156: $R(x,y)\le By^{x-1}\log\log y/\log y$ for $x\ge3$ , where the paper's $R(x,y)$ is the largest order of a graph with no $K_x$ and no $y$ independent vertices, one less than the usual Ramsey number. The paper prints no chromatic-number statement; the site's display is the form Erdős's 1969 survey gives it, and the library card records the translation to $f_k(n)$ with a filing observation on the exponent of the logarithmic factor for $k\ge4$ . Library home: Corollary (Graver and Yackel 1968).
MaVe23: Mattheus, S. and Verstraete, J., The asymptotics of $r(4,t)$ . Ann. of Math. (2) 199 (2024), no. 2, 919--941, DOI 10.4007/annals.2024.199.2.8; arXiv:2306.04007 (2023).

Problem 920

Status

Proof claims

Discussion