Hostname: page-component-586b7cd67f-gb8f7 Total loading time: 0 Render date: 2024-11-30T04:25:29.462Z 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: [email protected])
DERYK OSTHUS
Affiliation:
Institut für Informatik, Humboldt-Universität zu Berlin, Unter den Linden 6, D – 10099 Berlin, Germany (e-mail: [email protected])

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
Copyright
2004 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)