Is it true that $f_2(n) \gg n$? Disproved by Rödl, who showed $f_r(n) = o(n)$ for all fixed $r \geq 2$. A conjecture of Erdős, Hajnal, and Szemerédi.

Is it true that $f_2(n) \gg n$? Disproved by Rödl, who showed $f_r(n) = o(n)$ for all fixed $r \geq 2$. A conjecture of Erdős, Hajnal, and Szemerédi.

This seems to be closely related to, but distinct from, 744.

Tang notes in the comments that Rödl [Ro82] constructed, for any $\epsilon>0$ and $k$, a graph with chromatic number $\geq k$ such that every graph on $m$ vertices is bipartite after deleting at most $\epsilon m$ edges.