OPENHARDgraph theory
Can every triangle-free graph on $5n$ vertices be made bipartite by deleting at most $n^2$ edges?
Notes: The blow-up of C_5 shows this would be optimal. Balogh, Clemen, and Lidicky proved that deleting at most 1.064*n^2 edges suffices.
AI Status: NONE · 0 total attempts