Erdős-Pósa property of chordless cycles and its applications

DOI10.1016/J.JCTB.2020.05.002MaRDI QIDQ2200918zbMATH OpenOpenAlexFDO

Authors Eun Jung Kim, O-joung Kwon

Publication date 24 September 2020

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

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://doi.org/10.1016/j.jctb.2020.05.002

zbMATH Keywords

holeschordal graphsErdős-Pósa property

Mathematics Subject Classification ID

Distance in graphs (05C12) Paths and cycles (05C38)

Recommendations

• Erdős-Pósa property of chordless cycles and its applications
• Approximation and kernelization for chordal vertex deletion
• Approximation and kernelization for chordal vertex deletion
• Erdős–Pósa property of obstructions to interval graphs
• Disjoint cycles intersecting a set of vertices

Cites work

• A new proof and generalizations of a theorem of Erdős and Pósa on graphs withoutk+1 independent circuits
• A tight Erdős-Pósa function for long cycles
• A tighter Erdős-Pósa function for long cycles
• A unified Erdős-Pósa theorem for constrained cycles
• Approximation and kernelization for chordal vertex deletion
• Chordal deletion is fixed-parameter tractable
• Disjoint cycles intersecting a set of vertices
• Feedback vertex set inspired kernel for chordal vertex deletion
• Graph minors. V. Excluding a planar graph
• Long cycles through prescribed vertices have the Erdős-Pósa property
• Mangoes and blueberries
• On Independent Circuits Contained in a Graph
• On the presence of disjoint subgraphs of a specified type
• Packing and covering immersion-expansions of planar sub-cubic graphs
• Packing cycles in graphs
• Packing cycles through prescribed vertices
• Packing directed circuits
• Packing directed circuits through prescribed vertices bounded fractionally
• Polylogarithmic approximation algorithms for weighted-\(\mathcal{F}\)-deletion problems
• Recent techniques and results on the Erdős-Pósa property
• The Erdős-Pósa property for edge-disjoint immersions in 4-edge-connected graphs
• The Erdős-Pósa property for long circuits

Cited in

(13)

• Structural parameterizations with modulator oblivion
• Packing and covering induced subdivisions
• On the feedback number of 3-uniform linear extremal hypergraphs
• On the Erdős–Pósa Property for Long Holes in \(\boldsymbol{C_4}\)-Free Graphs
• scientific article; zbMATH DE number 7765420 (Why is no real title available?)
• A unified Erdős-Pósa theorem for constrained cycles
• Towards a conjecture of Birmelé–Bondy–Reed on the Erdős–Pósa property of long cycles
• Erdős-Pósa property of chordless cycles and its applications
• The Erdős-Pósa property for long circuits
• Erdős–Pósa property of obstructions to interval graphs
• Erdös-Pósa Property of Obstructions to Interval Graphs
• The Erdős-Pósa property for odd cycles in highly connected graphs
• Towards constant-factor approximation for chordal/distance-hereditary vertex deletion

This page was built for publication: Erdős-Pósa property of chordless cycles and its applications

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