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

DOI10.1016/J.JCTB.2017.01.004MaRDI QIDQ2396891zbMATH OpenOpenAlexFDO

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

Publication date 26 May 2017

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

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

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)

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.

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

Cites work

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

Cited in

(20)

• Long cycles through prescribed vertices have the Erdős-Pósa property
• The edge-Erdős-Pósa property
• On the Erdős–Pósa Property for Long Holes in \(\boldsymbol{C_4}\)-Free Graphs
• Frames, \(A\)-paths, and the 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
• In absence of long chordless cycles, large tree-width becomes a local phenomenon
• Quadratic upper bounds on the Erdős--Pósa property for a generalization of packing and covering cycles
• Random graphs with few disjoint cycles
• Towards a conjecture of Birmelé–Bondy–Reed on the Erdős–Pósa property of long cycles
• A tight Erdős-Pósa function for wheel minors
• The Erdős-Pósa property for long circuits
• \(K_4\)-expansions have the edge-Erdős-Pósa property
• Erdős-Pósa from ball packing
• Erdős–Pósa property of obstructions to interval graphs
• Packing and covering induced subdivisions
• A unified Erdős-Pósa theorem for constrained cycles
• A tighter Erdős-Pósa function for long cycles
• Erdős-Pósa property of chordless cycles and its applications
• 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)