Existence of Spanning ℱ-Free Subgraphs with Large Minimum Degree. (7th December 2016)

• Record Type: Journal Article
• Authors: PERARNAU, G.; REED, B.
• Is Part Of: Combinatorics, probability and computing. Volume 26:Number 3(2017:May)
• Page Start: 448
• Page End: 467
• Publication Date: 2016-12-07
• Subjects: Primary 05C35, -- Secondary 05D40; Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548316000328
• Languages: English
• ISSNs: 0963-5483

Abstract

Abstract : Let ℱ be a family of graphs and let d be large enough. For every d -regular graph G, we study the existence of a spanning ℱ-free subgraph of G with large minimum degree. This problem is well understood if ℱ 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.