Odd-cycle transversal in triangle-free graphs

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

Let $G=(V,E)$ be a finite simple graph, $n=|V|$, and suppose $G$ has no triangle. A set $F\subseteq E$ is an odd-cycle edge transversal if every cycle of odd length contains an edge of $F$; equivalently, $G-F$ is bipartite.

Statement recorded in the supplied source.

Does every such $G$ have an odd-cycle edge transversal $F$ satisfying $|F|\leq n^2/25$? Equivalently, does $G$ admit a vertex bipartition having at most $n^2/25$ edges within its parts? [S2]

Short English statement

Can every triangle-free graph be made bipartite by deleting at most one twenty-fifth of the square of its number of vertices?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 3285 (OPG-46824). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Odd-cycle transversal in triangle-free graphs, node 46824, original problem page. Original question and full discussion. https://www.openproblemgarden.org/op/odd_cycle_transversal_in_triangle_free_graphs.