Hostname: page-component-74656f9884-npj9w Total loading time: 0 Render date: 2026-11-09T05:03:50.741Z 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: kuehn@math.uni-hamburg.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.hu-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.

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

Information

Type
Paper
Copyright
© 2004 Cambridge University Press