Odd-cycle transversal in triangle-free graphs

Status partial high confidence

The conjecture that every triangle-free graph on $n$ vertices can be made bipartite by deleting at most $n^2/25$ edges remains open. Balogh, Clemen, and Lidický (2021) proved it for triangle-free graphs with edge density at most $0.2486$ or at least $0.3197$, and improved the best general upper bound from $n^2/18$ to $n^2/23.5$. A related spectral approach by the same group and coauthors (2022) further investigated structural properties of triangle-free graphs, but the full conjecture is unresolved.

Cited literature (2)

• partial Max Cuts in Triangle-free Graphs (2021)
  József Balogh, Felix Christian Clemen, Bernard Lidický · arXiv preprint · arXiv:2103.14179

  Proves the Erdős–Faudree–Pach–Spencer conjecture for triangle-free graphs with edge density at most 0.2486 or at least 0.3197, and improves the general upper bound on edges to delete to achieve bipartiteness from $n^2/18$ to $n^2/23.5$.

• partial The Spectrum of Triangle-free Graphs (2022)
  József Balogh, Felix Christian Clemen, Bernard Lidický, Sergey Norin, Jan Volec · SIAM Journal on Discrete Mathematics · arXiv:2204.00093 · doi:10.1137/22M150767X

  Via flag algebra and spectral methods, proves bounds on the smallest eigenvalue of the signless Laplacian of triangle-free graphs, with progress toward structural results related to the bipartization conjecture.

Reviewer notes. The ScienceDirect page for '10 problems for partitions of triangle-free graphs' (2023) returned HTTP 403 and could not be verified; it may contain additional partial results. The UCSD Erdős problems page (mathweb.ucsd.edu) returned a certificate error and could not be fetched. The extremal bound n²/25 is tight, realized by the balanced blow-up of C₅. The 2022 spectral paper (arXiv:2204.00093) is published in SIAM J. Discrete Math. (doi confirmed in search results) but the exact contribution to the n²/25 bound could not be fully characterized from the abstract alone.

Auto-reviewed 2026-05-08 with claude-sonnet-4-6 (worker 03) (web search enabled).