Hostname: page-component-586b7cd67f-rdxmf Total loading time: 0 Render date: 2024-11-24T23:39:20.488Z Has data issue: false hasContentIssue false

Large Topological Cliques in Graphs Without a 4-Cycle

Published online by Cambridge University Press:  19 January 2004

DANIELA KÜHN
Affiliation:
Mathematisches Seminar, Universität Hamburg, Bundesstraße 55, D – 20146 Hamburg, 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

Mader asked whether every $C_4$-free graph $G$ contains a subdivision of a complete graph whose order is at least linear in the average degree of $G$. We show that there is a subdivision of a complete graph whose order is almost linear. More generally, we prove that every $K_{s,t}$-free graph of average degree $r$ contains a subdivision of a complete graph of order $r^{\frac{1}{2}{+}\frac{1}{2(s-1)}-o(1)}$.

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