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

DOI10.4230/LIPICS.STACS.2018.7zbMATH Open1490.05205OpenAlexW2793394636MaRDI QIDQ3304101FDOQ3304101

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

Publication date: 5 August 2020

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

Recommendations

• Erdős–Pósa property of obstructions to interval graphs
• Adjacency properties of graphs and a conjecture of Erdős
• The Erdős-Pósa property for odd cycles in graphs of large connectivity
• Erdős-Pósa property of chordless cycles and its applications
• Erdős-Pósa property of chordless cycles and its applications
• The Erdős-Pósa property for odd cycles in highly connected graphs
• An edge variant of the Erdős-Pósa property
• The Erdős-Pósa property for clique minors in highly connected graphs
• Graphs with the Erdős-Ko-Rado property
• De Bruijn-Erdős-type theorems for graphs and posets

zbMATH Keywords

interval graphsobstructionsErdős-Pósa property

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Graph Classes: A Survey
• Title not available (Why is that?)
• Non-zero disjoint cycles in highly connected group labelled graphs
• Graph minors. V. Excluding a planar graph
• Mangoes and blueberries
• Quickly excluding a planar graph
• On Independent Circuits Contained in a Graph
• Approximate min-max relations for odd cycles in planar graphs
• Highly parity linked graphs
• Large-treewidth graph decompositions and applications
• A Minimax Theorem for Directed Graphs
• Packing cycles through prescribed vertices
• Covering a hypergraph of subgraphs
• Title not available (Why is that?)
• The Erdős-Pósa property for odd cycles in graphs of large connectivity
• Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
• Interval deletion is fixed-parameter tractable
• Packing directed circuits
• Packing circuits in eulerian digraphs
• The Erdös-Pósa property for matroid circuits
• Parity Linkage and the Erdős–Pósa Property of Odd Cycles through Prescribed Vertices in Highly Connected Graphs
• Disjoint cycles intersecting a set of vertices
• Linear recognition of almost interval graphs
• The Erdős-Pósa property for odd cycles in highly connected graphs
• Packing directed circuits exactly
• 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
• The Erdős-Pósa property for long circuits
• VC-dimension and Erdős-Pósa property
• Packing and covering immersion-expansions of planar sub-cubic graphs
• Two disjoint negative cycles in a signed graph
• Fixed-parameter tractability for subset feedback set problems with parity constraints

Cited In (2)

• Erdős–Pósa property of obstructions to interval graphs
• Recent techniques and results on the Erdős-Pósa property

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

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