Finding subgraphs with large girth and chromatic number

A conjecture on subgraphs of given chromatic number and girth (As proposed by by Erdos and Hajnal [2])

For integers \(k\) and \(r\), there is a function \(f(k,r)\) such that every graph with chromatic number at least \(f(k,r)\) contains a subgraph with chromatic number \(\geq k\) and girth \(\geq r\).

Rödl [1] proved the above conjecture for the case of \( r=4\) and all \( k\). However, his upper bound is quite large. Erdos [2] further asked: Is it true that

\(\displaystyle \lim_{k \rightarrow \infty} \frac{f(k,r+1)}{f(k,r)} = \infty? \)

1 V. Rödl, On the chromatic number of subgraphs of a given graph, Proc. Amer. Math. Soc. 64 (1977), 370-371.

2 P. Erdös, Problems and results in graph theory and combinatorial analysis, Graph theory and related topics (Proc. Conf., Univ. Waterloo, Waterloo, Ont., 1977), 153-163, Academic Press, New York-London, 1979.