Problem 111

Erdős Problem #111: declared status 'open'. Formalized: no. If $G$ is a graph let $h_G(n)$ be defined such that any subgraph of $G$ on $n$ vertices can be made bipartite after deleting at most $h_G(n)$ edges. What is the behaviour of $h_G(n)$? Is it true that $h_G(n)/n\to \infty$ for every graph $G$ with chromatic number $\aleph_1$? Current best: In [Er81] Erd\H{o}s conjectured that this can be improved to $\ll n^{1+\epsilon}$ for every $\epsilon>0$. Prize: no. Tags: chromatic number, graph theory, set theory.