Problem Statement
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$?
Categories:
Graph Theory Chromatic Number Cycles
Progress
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.
Source: erdosproblems.com/108 | Last verified: January 13, 2026