OPEN
This is open, and cannot be resolved with a finite computation.
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$?
A problem of Erdős, Hajnal, and Szemerédi
[EHS82]. Every $G$ with chromatic number $\aleph_1$ must have $h_G(n)\gg n$ since $G$ must contain, for some $r$, $\aleph_1$ many vertex disjoint odd cycles of length $2r+1$.
On the other hand, Erdős, Hajnal, and Szemerédi proved that there is a $G$ with chromatic number $\aleph_1$ such that $h_G(n)\ll n^{3/2}$. In
[Er81] Erdős conjectured that this can be improved to $\ll n^{1+\epsilon}$ for every $\epsilon>0$.
See also
[74].
View the LaTeX source
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #111, https://www.erdosproblems.com/111, accessed 2026-01-16
