Article contents
Large Topological Cliques in Graphs Without a 4-Cycle
Published online by Cambridge University Press: 19 January 2004
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
- Copyright
- © 2004 Cambridge University Press
- 7
- Cited by