Erdös-Pósa Property of Obstructions to Interval Graphs

DOI10.4230/LIPIcs.STACS.2018.7zbMath1490.05205OpenAlexW2793394636MaRDI QIDQ3304101

Daniel Lokshtanov, Saket Saurabh, Akanksha Agrawal, Meirav Zehavi, Pranabendu Misra

Publication date: 5 August 2020

Full work available at URL: https://doi.org/10.4230/LIPIcs.STACS.2018.7

zbMATH Keywords

obstructionsinterval graphsErdős-Pósa property

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph representations (geometric and intersection representations, etc.) (05C62)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Packing directed circuits exactly
• Disjoint cycles intersecting a set of vertices
• Approximate min-max relations for odd cycles in planar graphs
• Highly parity linked graphs
• The Erdös-Pósa property for matroid circuits
• Graph minors. V. Excluding a planar graph
• Mangoes and blueberries
• Quickly excluding a planar graph
• Packing directed circuits
• Covering a hypergraph of subgraphs
• Packing circuits in eulerian digraphs
• Packing cycles through prescribed vertices
• Fixed-parameter tractability for subset feedback set problems with parity constraints
• A tight Erdős-Pósa function for long cycles
• Packing and covering immersion-expansions of planar sub-cubic graphs
• The Erdős-Pósa property for long circuits
• Non-zero disjoint cycles in highly connected group labelled graphs
• VC-dimension and Erdős-Pósa property
• Two disjoint negative cycles in a signed graph
• Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
• A Minimax Theorem for Directed Graphs
• Graph Classes: A Survey
• Linear Recognition of Almost Interval Graphs
• Interval Deletion Is Fixed-Parameter Tractable
• Parity Linkage and the Erdős–Pósa Property of Odd Cycles through Prescribed Vertices in Highly Connected 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
• The Erdős-Pósa property for odd cycles in highly connected graphs
• The Erdős-Pósa property for odd cycles in graphs of large connectivity

This page was built for publication: Erdös-Pósa Property of Obstructions to Interval Graphs