Erdős Problem #1013

declared status 'open'. Formalized: no. 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.$$ Current best: 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]. Prize: no. OEIS: A292528. Tags: graph theory.

Notation is rendered from the stored source. The pinned checkout remains the exact record.