No CrossRef data available.
Published online by Cambridge University Press: 19 January 2004
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)}$.