Extremal connectivity for topological cliques in bipartite graphs

DOI10.1016/J.JCTB.2005.06.005MaRDI QIDQ2581501zbMATH OpenOpenAlexFDO

Authors Deryk Osthus, Daniela Kühn

Publication date 10 January 2006

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jctb.2005.06.005

zbMATH Keywords

subdivisionstopological minors

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Connectivity (05C40) Random graphs (graph-theoretic aspects) (05C80)

Review text

Given a natural number \(s\), let \(d(s)\) be the smallest number such that every graph of average degree greater than \(d(s)\) contains a subdivision of the complete graph of order \(s\). The authors establish a lower bound of \(d(s)\) for bipartite graphs whose connectivity is close to their average degree.

Recommendations

• Topological minors in bipartite graphs
• Topological Cliques in Graphs
• Bipartite subgraphs of graphs with maximum degree three
• More on the extremal number of subdivisions
• Extremal density for sparse minors and subdivisions

Cites work

• Eine Verallgemeinerung des n-fachen Zusammenhangs für Graphen
• Existenz n-fach zusammenhängender Teilgraphen in Graphen genügend großer Kantendichte
• Grad und lokaler Zusammenhang in endlichen Graphen
• Homomorphieeigenschaften und mittlere Kantendichte von Graphen
• scientific article; zbMATH DE number 3652373 (Why is no real title available?)
• scientific article; zbMATH DE number 52938 (Why is no real title available?)
• scientific article; zbMATH DE number 1179517 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 1870233 (Why is no real title available?)
• scientific article; zbMATH DE number 878896 (Why is no real title available?)
• Linear connectivity forces large complete bipartite minors
• On graphs with small subgraphs of large chromatic number
• Proof of a conjecture of Mader, Erdős and Hajnal on topological complete subgraphs
• Random graphs.
• The extremal function for complete minors
• Topological cliques in graphs II
• Two Minor Problems

Cited in

(6)

• A note on the saturation number of the family of \(k\)-connected graphs
• Logarithmically small minors and topological minors
• Local conditions for exponentially many subdivisions
• Topological minors in bipartite graphs
• Immersion of complete digraphs in Eulerian digraphs
• Packing subdivisions into regular graphs

This page was built for publication: Extremal connectivity for topological cliques in bipartite graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2581501)