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

DOI10.1016/j.jctb.2017.01.004zbMath1362.05106arXiv1603.07588OpenAlexW2306414598MaRDI QIDQ2396891

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)

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

zbMATH Keywords

Erdős-Pósa propertylong cyclescovering vs packing

Mathematics Subject Classification ID

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

Related Items (13)

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 ⋮ Towards a conjecture of Birmelé–Bondy–Reed on the Erdős–Pósa property of long cycles ⋮ \(K_4\)-expansions have the edge-Erdős-Pósa property ⋮ Erdős–Pósa property of obstructions to interval graphs ⋮ On the Erdős–Pósa Property for Long Holes in \(\boldsymbol{C_4}\)-Free Graphs ⋮ Erdős-Pósa property of chordless cycles and its applications ⋮ A Tight Erdös--Pósa Function for Wheel Minors ⋮ Erdös--Pósa from Ball Packing ⋮ Packing and Covering Induced Subdivisions ⋮ Graphs without two vertex-disjoint \(S\)-cycles ⋮ In absence of long chordless cycles, large tree-width becomes a local phenomenon

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Disjoint cycles intersecting a set of vertices
• Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs
• Ramanujan graphs
• Packing cycles through prescribed vertices
• The Erdős-Pósa property for long circuits
• A Tighter Erdős-Pósa Function for Long Cycles
• On the presence of disjoint subgraphs of a specified type
• Long cycles through prescribed vertices have the Erdős‐Pósa property
• Tree-width and circumference of graphs
• On Independent Circuits Contained in a Graph
• Large-treewidth graph decompositions and applications
• A new proof and generalizations of a theorem of Erdős and Pósa on graphs withoutk+1 independent circuits

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