DISPROVED
This has been solved in the negative.
Let $k$ be a large fixed constant. Let $f_k(n)$ be the minimal $m$ such that there exists a graph $G$ on $n$ vertices with chromatic number $k$, such that every proper subgraph has chromatic number $<k$, and $G$ can be made bipartite by deleting $m$ edges.
Is it true that $f_k(n)\to \infty$ as $n\to \infty$? In particular, is it true that $f_4(n) \gg \log n$?
A problem of Erdős, Hajnal, and Szemerédi
[EHS82]. Odd cycles show that $f_3(n)=1$, but they expected $f_4(n)\to \infty$. Gallai
[Ga68] gave a construction which shows\[f_4(n) \ll n^{1/2},\]and Lovász extended this to show\[f_k(n) \ll n^{1-\frac{1}{k-2}}.\]This conjecture was disproved by Rödl and Tuza
[RoTu85], who proved that in fact $f_k(n)=\binom{k-1}{2}$ (for all sufficiently large $n$).
View the LaTeX source
This page was last edited 01 January 2026.
Additional thanks to: Raphael Steiner
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 #744, https://www.erdosproblems.com/744, accessed 2026-01-16
