Article contents
Subdivisions of $K_{r+2}$ in Graphs of Average Degree at Least $r+\varepsilon$ and Large but Constant Girth
Published online by Cambridge University Press: 28 April 2004
Abstract
We show that for every $\varepsilon\,{>}\,0$ there exists an $r_0\,{=}\,r_0(\varepsilon)$ such that, for all integers $r\,{\ge}\, r_0$, every graph of average degree at least $r+\varepsilon$ and girth at least 1000 contains a subdivision of $K_{r+2}$. Combined with a result of Mader this implies that, for every $\varepsilon\,{>}\,0$, there exists an $f(\varepsilon)$ such that, for all $r\,{\ge}\, 2$, every graph of average degree at least $r+\varepsilon$ and girth at least $f(\varepsilon)$ contains a subdivision of $K_{r+2}$. We also prove a more general result concerning subdivisions of arbitrary graphs.
- Type
- Paper
- Information
- Copyright
- 2004 Cambridge University Press
- 2
- Cited by