Problem #620: If $G$ is a graph on $n$ vertices without a $K_4$ then how...

---

Progress

This was first asked by Erdős and Rogers [ErRo62], and is generally known as the Erdős-Rogers problem. Let $f(n)$ be such that every such graph contains a triangle-free subgraph with at least $f(n)$ vertices.

It is now known that $f(n)=n^{1/2+o(1)}$. Bollobás and Hind [BoHi91] proved\[n^{1/2} \ll f(n) \ll n^{7/10+o(1)}.\]Krivelevich [Kr94] improved this to\[n^{1/2}(\log\log n)^{1/2} \ll f(n) \ll n^{2/3}(\log n)^{1/3}.\]Wolfovitz [Wo13] proved\[f(n) \ll n^{1/2}(\log n)^{120}.\]The best bounds currently known are\[n^{1/2}\frac{(\log n)^{1/2}}{\log\log n}\ll f(n) \ll n^{1/2}\log n.\]The lower bound follows from results of Shearer [Sh95], and the upper bound was proved by Mubayi and Verstraete [MuVe24].