Logo
All Random Solved Random Open
OPEN
Can every triangle-free graph on $5n$ vertices be made bipartite by deleting at most $n^2$ edges?
The blow-up of $C_5$ shows that this would be the best possible. The best known bound is due to Balogh, Clemen, and Lidicky [BCL21], who proved that deleting at most $1.064n^2$ edges suffices.

See also the entry in the graphs problem collection.

Additional thanks to: Casey Tompkins