Induced subdivisions in K_s,s-free graphs of large average degree
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.
- A proof of Mader's conjecture on large clique subdivisions in \(C_4\)-free graphs
- Subdivisions of $K_{r+2}$ in Graphs of Average Degree at Least $r+\varepsilon$ and Large but Constant Girth
- Induced subdivisions and bounded expansion
- Complete minors in \(K_{s,s}\)-free graphs
- Subdivisions of a large clique in \(C_6\)-free graphs
- Excluding subdivisions of bounded degree graphs
- Induced subdivisions and bounded expansion
- Chromatic number of ISK4-free graphs
- From \(\chi\)- to \(\chi_p\)-bounded classes
- Tree-width dichotomy
- The chromatic number of graphs with no induced subdivision of \(K_4\)
- Complete acyclic colorings
- Regular partitions of gentle graphs
- In absence of long chordless cycles, large tree-width becomes a local phenomenon
- Subdivisions of a large clique in \(C_6\)-free graphs
- Coloring graphs with no even hole \(\geqslant 6\): the triangle-free case
- Clique cutsets beyond chordal graphs
- Vertex elimination orderings for hereditary graph classes
- Unavoidable induced subgraphs in large graphs with no homogeneous sets
- Degeneracy of \(P_t\)-free and \(C_{\geq t}\)-free graphs with no large complete bipartite subgraphs
- Amalgams and -boundedness
- On Triangle-Free Graphs That Do Not Contain a Subdivision of the Complete Graph on Four Vertices as an Induced Subgraph
- A separator theorem for string graphs and its applications
- A Separator Theorem for String Graphs and Its Applications
- On graphs with no induced subdivision of \(K_4\)
- Subdivisions of large complete bipartite graphs and long induced paths in k‐connected graphs
- The structure of (theta, pyramid, 1-wheel, 3-wheel)-free graphs
- Implicit representations and factorial properties of graphs
- Subdivisions of $K_{r+2}$ in Graphs of Average Degree at Least $r+\varepsilon$ and Large but Constant Girth
- A class of three-colorable triangle-free graphs
- Dense Induced Subgraphs of Dense Bipartite Graphs
- A proof of Mader's conjecture on large clique subdivisions in \(C_4\)-free graphs
- Triangle‐free graphs with large chromatic number and no induced wheel
- The chromatic number of {ISK4, diamond, bowtie}‐free graphs
- Some remarks on graphs with no induced subdivision of \(K_4\)
- Induced subgraphs and tree decompositions. IV: (Even hole, diamond, pyramid)-free graphs
- Hitting all maximum stable sets in P₅-free graphs
- Graphs of large chromatic number
- Topological minors in bipartite graphs
- Sparse graphs with bounded induced cycle packing number have logarithmic treewidth
- Induced subdivisions with pinned branch vertices
- Chi-boundedness of graphs containing no cycles with k chords
- A survey of degree-boundedness
- Excluding a clique or a biclique in graphs of bounded induced matching treewidth
- Induced C₄-free subgraphs with large average degree
- Sparse induced subgraphs of large treewidth
- Kővári-Sós-Turán theorem for hereditary families
- Shift graphs, chromatic number and acyclic one-path orientations
- Combinatorics. Abstracts from the workshop held January 4--9, 2026
This page was built for publication: Induced subdivisions in \(K_{s,s}\)-free graphs of large average degree
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q705743)
