# 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?$$

Bibliography
1 V. Rödl, On the chromatic number of subgraphs of a given graph, Proc. Amer. Math. Soc. 64 (1977), 370-371. http://www.springerlink.com/content/95r2438500162193/

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.