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

obstructions interval graphs Erdős-Pósa property

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