Induced subdivisions in \(K_{s,s}\)-free graphs of large average degree (Q705743)

The paper strengthen the classical result of Mader on graph embedding. It had been stated that for every graph \(H\) there exists a number \(d=d(H)\) such that every graph \(G\) of average degree at least \(d\) contains a subdivision of \(H\). The authors show that provided the extra assumption that the host graph \(G\) is \(K_{s, s}\)-free, \(G\) contains even an induced subdivision of \(H\). The are a number of related results that makes the above embedding interesting. In special cases \textit{H. A. Kierstead} and \textit{S. G. Penrice} [J. Graph Theory 18, 119--129 (1994; Zbl 0798.05023)] proved that if \(H\) is a tree, then it can be found as an induced subgraph of any \(K_{s, s}\)-free graph \(G\), provided the average degree of \(G\) is great enough. That result can be used in proofs of some cases of conjectures of \textit{A. Gyárfás} [Infinite finite Sets, Colloq. Honour Paul Erdős, Keszthely 1973, Colloq. Math. Soc. Janos Bolyai 10, 801--816 (1975; Zbl 0307.05111)], and \textit{D. P. Sumner} [The theory and applications of graphs, 4th int. Conf., Kalamazoo/Mich. 1980, 557--576 (1981; Zbl 0476.05037)]. The proof is quite complicated and uses probabilistic methods.