Erdős–Pósa property of obstructions to interval graphs

DOI10.1002/jgt.22895zbMath1522.05359MaRDI QIDQ6094044

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

Publication date: 9 October 2023

Published in: Journal of Graph Theory (Search for Journal in Brave)

zbMATH Keywords

interval graphsErdős-Pósa propertyasteroidal witness

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• Erdős-Pósa property of chordless cycles and its applications
• 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
• Recent techniques and results on the Erdős-Pósa property
• 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
• Representation of a finite graph by a set of intervals on the real line
• 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
• Long cycles through prescribed vertices have the Erdős‐Pósa property
• 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