Existence of spanning F-free subgraphs with large minimum degree

DOI10.1017/S0963548316000328MaRDI QIDQ5366947zbMATH OpenFDO

Authors Guillem Perarnau, Bruce Reed

Publication date 10 October 2017

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1404.7764

zbMATH Keywords

bipartite graphs

Mathematics Subject Classification ID

Vertex degrees (05C07) Extremal problems in graph theory (05C35) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Abstract: Let $mathcalF$ be a family of fixed graphs and let $d$ be large enough. For every $d$-regular graph $G$, we study the existence of a spanning $mathcalF$-free subgraph of $G$ with large minimum degree. This problem is well-understood if $mathcalF$ does not contain bipartite graphs. Here we provide asymptotically tight results for many families of bipartite graphs such as cycles or complete bipartite graphs.

Recommendations

• Regular spanning subgraphs of bipartite graphs of high minimum degree
• Large subgraphs without short cycles
• Embedding large subgraphs into dense graphs
• Spanning trees in dense graphs
• Irregular subgraphs

Cites work

• A note on graphs without short even cycles
• Every graph of sufficiently large average degree contains a C₄-free subgraph of large average degree
• Extensions of Sylvester's Theorem
• Girth in graphs
• Graph colouring and the probabilistic method
• Graph Theory and Probability
• Graph Theory and Probability. II
• scientific article; zbMATH DE number 4164908 (Why is no real title available?)
• scientific article; zbMATH DE number 3232670 (Why is no real title available?)
• scientific article; zbMATH DE number 3333193 (Why is no real title available?)
• Large subgraphs without short cycles
• Norm-graphs and bipartite Turán numbers
• Norm-graphs: Variations and applications
• On a conjecture of Thomassen
• On a problem of K. Zarankiewicz
• Polarities and \(2k\)-cycle-free graphs
• Short proofs of some extremal results. II.
• The history of degenerate (bipartite) extremal graph problems

Cited in

(14)

• Regular spanning subgraphs of bipartite graphs of high minimum degree
• Subgraphs with large minimum \(\ell\)-degree in hypergraphs where almost all \(\ell\)-degrees are large
• Relative Turán numbers for hypergraph cycles
• Inverse Turán numbers
• Degree Ramsey numbers for even cycles
• Large subgraphs without short cycles
• Decomposition of bounded degree graphs into \(C_4\)-free subgraphs
• Relative Turán problems for uniform hypergraphs
• Counting hypergraphs with large girth
• Random polynomial graphs for random Turán problems
• Minimum degree conditions for containing an \(r\)-regular \(r\)-connected spanning subgraph
• The automorphism group of projective norm graphs
• Spanning subdivisions in Dirac graphs
• Subgraphs of the projective norm graph

This page was built for publication: Existence of spanning \(\mathcal{F}\)-free subgraphs with large minimum degree

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