Existence of Spanning F-Free Subgraphs with Large Minimum Degree

Guillem Perarnau, Bruce Reed

Research output: Contribution to journalArticlepeer-review

127 Downloads (Pure)

Abstract

Let F be a family of 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 wellunderstood 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. To prove these results, we study a locally injective analogue of the question.
Original languageEnglish
JournalCombinatorics, Probability and Computing
Early online date7 Dec 2016
DOIs
Publication statusE-pub ahead of print - 7 Dec 2016

Fingerprint

Dive into the research topics of 'Existence of Spanning F-Free Subgraphs with Large Minimum Degree'. Together they form a unique fingerprint.

Cite this