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), 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.
|