Hostname: page-component-cd9895bd7-lnqnp Total loading time: 0 Render date: 2024-12-18T04:31:50.267Z Has data issue: false hasContentIssue false
  • English
  • Français

Large Topological Cliques in Graphs Without a 4-Cycle

Published online by Cambridge University Press:  19 January 2004

DANIELA KÜHN  and
DERYK OSTHUS
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])
Get access Rights & Permissions [Opens in a new window]

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
Information
Combinatorics, Probability and Computing , Volume 13 , Issue 1 , January 2004 , pp. 93 - 102
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.)