Hostname: page-component-7b7567c8c-z4zkx Total loading time: 0 Render date: 2026-11-18T05:35:20.224Z Has data issue: false hasContentIssue false

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

DANIELA KÜHN
Affiliation:
Freie Universität Berlin, Institut für Mathematik, Arnimallee 2–6, D – 14195 Berlin, Germany (e-mail: dkuehn@math.fu-berlin.de)
DERYK OSTHUS
Affiliation:
Institut für Informatik, Humboldt-Universität zu Berlin, Unter den Linden 6, D – 10099 Berlin, Germany (e-mail: osthus@informatik.fu-berlin.de)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

Type
Paper
Copyright
2004 Cambridge University Press