Logo
All Random Solved Random Open
OPEN
If $G$ is a graph on $n$ vertices without a $K_4$ then how large a triangle-free induced subgraph must $G$ contain?
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}.\]

Additional thanks to: Noga Alon