Existence of spanning $\mathcal{F}$-free subgraphs with large minimum degree

Abstract

Let $\mathcal{F}$ 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 $\mathcal{F}$-free subgraph of $G$ with large minimum degree. This problem is well-understood if $\mathcal{F}$ does not contain bipartite graphs. Here we provide asymptotically tight results for many families of bipartite graphs such as cycles or complete bipartite graphs.

22 pages

References in corpus (2)

• Large subgraphs without short cycles
• Large subgraphs without complete bipartite graphs

Cited by in corpus (2)

• Decomposition of bounded degree graphs into $C_4$-free subgraphs
• Relative Turán Problems for Uniform Hypergraphs