Existence of Spanning F-Free Subgraphs with Large Minimum Degree

Guillem Perarnau; Bruce Reed

doi:10.1017/S0963548316000328

Existence of Spanning F-Free Subgraphs with Large Minimum Degree

Guillem Perarnau, Bruce Reed

Mathematics

Research output: Contribution to journal › Article › peer-review

167 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 language	English
Journal	Combinatorics, Probability and Computing
Early online date	7 Dec 2016
DOIs	https://doi.org/10.1017/S0963548316000328
Publication status	E-pub ahead of print - 7 Dec 2016

Access to Document

10.1017/S0963548316000328Licence: None: All rights reserved

Perarnau_Existence_spanning_Combinatorics_Probability_Computing_2016
Eligibility for repository: Checked on 9/12/2016
Accepted author manuscript, 331 KBLicence: None: All rights reserved

Cite this

@article{913632e893b64ad1bfa8f9cf9aa036fa,

title = "Existence of Spanning F-Free Subgraphs with Large Minimum Degree",

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.",

author = "Guillem Perarnau and Bruce Reed",

year = "2016",

month = dec,

day = "7",

doi = "10.1017/S0963548316000328",

language = "English",

journal = "Combinatorics, Probability and Computing",

issn = "0963-5483",

publisher = "Cambridge University Press",

}

TY - JOUR

T1 - Existence of Spanning F-Free Subgraphs with Large Minimum Degree

AU - Perarnau, Guillem

AU - Reed, Bruce

PY - 2016/12/7

Y1 - 2016/12/7

N2 - 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.

AB - 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.

U2 - 10.1017/S0963548316000328

DO - 10.1017/S0963548316000328

M3 - Article

SN - 0963-5483

JO - Combinatorics, Probability and Computing

JF - Combinatorics, Probability and Computing

ER -

Existence of Spanning F-Free Subgraphs with Large Minimum Degree

Abstract

Access to Document

Fingerprint

Cite this