Induced subdivisions in \(K_{s,s}\)-free graphs of large average degree (Q705743): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/s00493-004-0017-8 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1965246637 / rank | |||
Normal rank |
Latest revision as of 02:12, 20 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Induced subdivisions in \(K_{s,s}\)-free graphs of large average degree |
scientific article |
Statements
Induced subdivisions in \(K_{s,s}\)-free graphs of large average degree (English)
0 references
14 February 2005
0 references
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.
0 references
graph embedding
0 references
average degree
0 references
Mader theorem
0 references