OPENNOTORIOUSgraph theorychromatic number
Let $f(n)\to \infty$ (possibly very slowly). Is there a graph of infinite chromatic number such that every finite subgraph on $n$ vertices can be made bipartite by deleting at most $f(n)$ edges?
Notes: Conjectured by Erdos, Hajnal, and Szemeredi. Rodl proved it for hypergraphs and for f(n) = epsilon*n. Open even for f(n) = sqrt(n). Fails for chromatic number aleph_1.
AI Status: NONE · 0 total attempts