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

DOI10.4230/LIPICS.STACS.2018.7MaRDI QIDQ3304101zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

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

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)