Problem #1011: Let $f_r(n)$ be minimal such that every graph on $n$...

---

Progress

Turán's theorem implies $f_2(n)=\lfloor n^2/4\rfloor+1$. Erdős and Gallai [Er62d] proved $f_3(n)=\lfloor \frac{1}{4}(n-1)^2\rfloor+2$.

Simonovits showed in his PhD thesis (see the discussion on p. 358 of [Si74]) that\[f_r(n)=\frac{n^2}{4}-\frac{g(r)}{2}{n}+O(1),\]where $g(r)$ is the largest $m$ such that, for any triangle-free graph with chromatic number $\geq r$, at least $m$ vertices of $G$ need to be removed to obtain a bipartite graph. Simonovits [Si74] notes\[\frac{\log r}{\log\log r}r^2 \ll g(r) \ll (\log r)^2r^2.\]Hunter in the comments has noted that other results imply $g(r)\asymp r^2\log r$ - in fact\[(1/2-o(1))r^2\log r\leq g(r)\leq (2+o(1))r^2\log r.\]The lower bound follows from work of Davies and Illingworth [DaIl22] (see [1104]). The upper bound follows from work of Hefty, Horn, King, and Pfender [HHKP25] on $R(3,k)$.

Ren, Wang, Wang, and Yang [RWWY24] showed that, for $n\geq 150$,\[f_4(n)=\left\lfloor\frac{(n-3)^2}{4}\right\rfloor+6.\]