OPEN
This is open, and cannot be resolved with a finite computation.
Let $h_3(k)$ be the minimal $n$ such that there exists a triangle-free graph on $n$ vertices with chromatic number $k$. Find an asymptotic for $h_3(k)$, and also prove\[\lim_{k\to \infty}\frac{h_3(k+1)}{h_3(k)}=1.\]
It is known that\[\frac{\log k}{\log\log k}k^2 \ll h_3(k) \ll (\log k)k^2.\]The lower bound is due to Graver and Yackel
[GrYa68], the upper bound follows from Shearer's upper bound for $R(3,k)$ (see
[165]).
The function $h_r(k)$ for $r\geq 4$ is the subject of
[920].
View the LaTeX source
This page was last edited 27 September 2025.
Additional thanks to: Sarosh Adenwalla and Stijn Cambie
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #1013, https://www.erdosproblems.com/1013, accessed 2026-01-16
