Existence of spanning F-free subgraphs with large minimum degree

2014/04/30 by Guillem Perarnau, Bruce Reed, Perarnau, Guillem +1 · 1 citation
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.1404.7764

openalex publication_date 2014/04/30 · openalex created_date 2016/12/16 · openalex updated_date 2026/07/28

Abstract

Let 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 F-free subgraph of G with large minimum degree. This problem is well-understood if 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.

Cited by

• Relative Turán Numbers for Hypergraph Cycles

Related

• Irregular Subgraphs
• Triangle-free subgraphs of random graphs
• Low chromatic spanning sub(di)graphs with prescribed degree or connectivity properties
• Unbounded degree spanning hypertrees in Dirac hypergraphs
• Large subgraphs without complete bipartite graphs