Problem Statement
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.\]
Categories:
Graph Theory Ramsey Theory
Progress
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].
Source: erdosproblems.com/1013 | Last verified: January 19, 2026