Finding subgraphs with large girth and chromatic number
Home
Search
Subjects
About Erdös
About This Site
Search
Subjects
 All (170)
 Ramsey Theory (40)
 Extremal Graph Theory (40)
 Coloring, Packing, and Covering (25)
 Random Graphs and Graph Enumeration (16)
 Hypergraphs (35)
 Infinite Graphs (14)
About Erdös
About This Site
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), 370371.
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), 153163, Academic Press, New
YorkLondon, 1979.
