A tight Erdős-Pósa function for long cycles

DOI10.1016/J.JCTB.2017.01.004zbMATH Open1362.05106arXiv1603.07588OpenAlexW2306414598MaRDI QIDQ2396891FDOQ2396891

Nemanja Škorić, Frank Mousset, Felix Weissenberger, Andreas Noever

Publication date: 26 May 2017

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Abstract: A classic result of ErdH{o}s and P'osa says that any graph contains either $k$ vertex-disjoint cycles or can be made acyclic by deleting at most $O(klogk)$ vertices. Here we generalize this result by showing that for all numbers $k$ and $l$ and for every graph $G$, either $G$ contains $k$ vertex-disjoint cycles of length at least $l$, or there exists a set $X$ of $mathcalO(kl+klogk)$ vertices that meets all cycles of length at least $l$ in $G$. As a corollary, the tree-width of any graph $G$ that does not contain $k$ vertex-disjoint cycles of length at least $l$ is of order $mathcalO(kl+klogk)$. These results improve on the work of Birmel'e, Bondy and Reed '07 and Fiorini and Herinckx '14 and are optimal up to constant factors.

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

Recommendations

• A tighter Erdős-Pósa function for long cycles
• The Erdős-Pósa property for long circuits
• The Erdös-Pósa property for long circuits
• Towards a conjecture of Birmelé–Bondy–Reed on the Erdős–Pósa property of long cycles
• The Erdős-Pósa property for long circuits

zbMATH Keywords

long cyclescovering vs packingErdős-Pósa property

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Distance in graphs (05C12) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Title not available (Why is that?)
• Ramanujan graphs
• On Independent Circuits Contained in a Graph
• Large-treewidth graph decompositions and applications
• Packing cycles through prescribed vertices
• Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs
• Tree-width and circumference of graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the presence of disjoint subgraphs of a specified type
• Disjoint cycles intersecting a set of vertices
• A new proof and generalizations of a theorem of Erdős and Pósa on graphs withoutk+1 independent circuits
• The Erdős-Pósa property for long circuits
• A tighter Erdős-Pósa function for long cycles
• Long cycles through prescribed vertices have the Erdős‐Pósa property
• The Erdős-Pósa Property for Long Circuits

Cited In (15)

• On the Erdős–Pósa Property for Long Holes in \(\boldsymbol{C_4}\)-Free Graphs
• The edge-Erdős-Pósa property
• Erdős-Pósa property of chordless cycles and its applications
• Erdös-Pósa Property of Obstructions to Interval Graphs
• A Tight Erdös--Pósa Function for Wheel Minors
• Erdös--Pósa from Ball Packing
• Packing and Covering Induced Subdivisions
• In absence of long chordless cycles, large tree-width becomes a local phenomenon
• Towards a conjecture of Birmelé–Bondy–Reed on the Erdős–Pósa property of long cycles
• The Erdős-Pósa property for long circuits
• \(K_4\)-expansions have the edge-Erdős-Pósa property
• Frames, $A$-Paths, and the Erdös--Pósa Property
• Erdős–Pósa property of obstructions to interval graphs
• A unified Erdős-Pósa theorem for constrained cycles
• Graphs without two vertex-disjoint \(S\)-cycles

This page was built for publication: A tight Erdős-Pósa function for long cycles

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