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?
A problem of Erdős, Gallai, and Tuza [EGT92]. The Erdős-Szekeres theorem (see [107]) implies that $G$ contains an independent set of size $\gg n^{1/3}$, so this is a lower bound.