Problem Statement
Let $g_k(n)$ denote the largest possible chromatic number of a graph with $n$ vertices which contains no $K_k$.
Is it true that, for $k\geq 4$,\[g_k(n) \gg \frac{n^{1-\frac{1}{k-1}}}{(\log n)^c}\]for some constant $c>0$?
Is it true that, for $k\geq 4$,\[g_k(n) \gg \frac{n^{1-\frac{1}{k-1}}}{(\log n)^c}\]for some constant $c>0$?
Categories:
Graph Theory Chromatic Number
Progress
Graver and Yackel [GrYa68] proved that\[g_k(n) \ll \left(n\frac{\log\log n}{\log n}\right)^{1-\frac{1}{k-1}}.\]Erdős [Er59b] proved that\[g_3(n) \gg \frac{n^{1/2}}{\log n},\]by proving $R(3,m)\gg (m/\log m)^2$. Shearer's lower bound for $R(3,m)$ (see [165]) improves this to\[g_3(n) \gg \left(\frac{n}{\log n}\right)^{1/2}.\]The lower bound $R(4,m) \gg m^3/(\log m)^4$ of Mattheus and Verstraete [MaVe23] (see [166]) implies\[g_4(n) \gg \frac{n^{2/3}}{(\log n)^{4/3}}.\]In general it is known (see [986]) that\[R(k,m)\gg (\log m)^{-O_k(1)}m^{\frac{k+1}{2}}\]which implies\[g_k(n) \gg \frac{n^{1-\frac{2}{k+1}}}{(\log n)^{c_k}}.\]See [1013] for the case $k=3$.Source: erdosproblems.com/920 | Last verified: January 19, 2026