Large subgraphs without short cycles

DOI10.1137/140954416zbMATH Open1327.05068arXiv1401.4928OpenAlexW2153561778MaRDI QIDQ3453565FDOQ3453565

Authors: Florent Foucaud, Michael Krivelevich, Guillem Perarnau 

Publication date: 27 November 2015

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: We study two extremal problems about subgraphs excluding a family $F$ of graphs. i) Among all graphs with $m$ edges, what is the smallest size $f(m,F)$ of a largest $F$--free subgraph? ii) Among all graphs with minimum degree $delta$ and maximum degree $Delta$, what is the smallest minimum degree $h(delta,Delta,F)$ of a spanning $F$--free subgraph with largest minimum degree? These questions are easy to answer for families not containing any bipartite graph. We study the case where $F$ is composed of all even cycles of length at most $2r$, $rgeq2$. In this case, we give bounds on $f(m,F)$ and $h(delta,Delta,F)$ that are essentially asymptotically tight up to a logarithmic factor. In particular for every graph $G$, we show the existence of subgraphs with arbitrarily high girth, and with either many edges or large minimum degree. These subgraphs are created using probabilistic embeddings of a graph into extremal graphs.

Full work available at URL: https://arxiv.org/abs/1401.4928

Recommendations

• An extremal problem for random graphs and the number of graphs with large even-girth
• On the structure of extremal graphs of high girth
• Existence of spanning \(\mathcal{F}\)-free subgraphs with large minimum degree
• Maximum bipartite subgraphs in graphs without short cycles
• Subgraphs with large degrees and girth

zbMATH Keywords

girthforbidden subgraphsspanning subgraphsprobabilistic methodsdegrees

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex degrees (05C07) Paths and cycles (05C38) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Cited In (14)

• Counting hypergraphs with large girth
• Random polynomial graphs for random Turán problems
• Large hypergraphs without tight cycles
• Inverse Turán numbers
• Expander spanning subgraphs with large girth
• Relative Turán problems for uniform hypergraphs
• Relative Turán numbers for hypergraph cycles
• LARGE -FREE SUBGRAPHS IN -CHROMATIC GRAPHS
• New examples of graphs without small cycles and of large size
• Short proofs of some extremal results. II.
• Triangle-free subgraphs of hypergraphs
• Inverting the Turán problem with chromatic number
• Existence of spanning \(\mathcal{F}\)-free subgraphs with large minimum degree
• Maximum cardinality neighbourly sets in quadrilateral free graphs

This page was built for publication: Large subgraphs without short cycles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3453565)