Conjectured by Erd\H{o}s, Hajnal, and Szemer\'{e}di \cite{EHS82}.

R\"{o}dl \cite{Ro82} has proved this for hypergraphs, and also proved there is such a graph (with chromatic number $\aleph_0$) if $f(n)=\epsilon n$ for any fixed constant $\epsilon>0$.

It is open even for $f(n)=\sqrt{n}$. Erd\H{o}s offered \$500 for a proof but only \$250 for a counterexample. This fails (even with $f(n)\gg n$) if the graph has chromatic number $\aleph_1$ (see [111]).


References


[EHS82] Erd\H{o}s, P. and Hajnal, A. and Szemer\'{e}di, E., On almost bipartite large chromatic graphs. Theory and practice of combinatorics (1982), 117-123.

[Ro82] R\"{o}dl, Vojt\vEch, Nearly bipartite graphs with large chromatic number. Combinatorica (1982), 377-383.