OPEN
This is open, and cannot be resolved with a finite computation.
For every $r\geq 4$ and $k\geq 2$ is there some finite $f(k,r)$ such that every graph of chromatic number $\geq f(k,r)$ contains a subgraph of girth $\geq r$ and chromatic number $\geq k$?
Conjectured by Erdős and Hajnal. Rödl
[Ro77] has proved the $r=4$ case (see
[923]). The infinite version (whether every graph of infinite chromatic number contains a subgraph of infinite chromatic number whose girth is $>k$) is also open.
In
[Er79b] Erdős also asks whether\[\lim_{k\to \infty}\frac{f(k,r+1)}{f(k,r)}=\infty.\]See also
the entry in the graphs problem collection and
[740] for the infinitary version.
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 #108, https://www.erdosproblems.com/108, accessed 2026-01-16
