Recent techniques and results on the Erdős-Pósa property

2016/03/15 by Jean‐Florent Raymond, Raymond, Jean-Florent, Dimitrios M. Thilikos +1 · 4 citations
Computer Science · Engineering · Mathematics · #05C70 #Advanced Graph Theory Research #Analytic Number Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.2.1 #G.2.2 #Limits and Structures in Graph Theory #Mathematical functions and polynomials #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.1603.04615

openalex publication_date 2016/03/15 · openalex created_date 2024/04/11 · openalex updated_date 2026/07/28

Abstract

Several min-max relations in graph theory can be expressed in the framework of the Erdős-Pósa property. Typically, this property reveals a connection between packing and covering problems on graphs. We describe some recent techniques for proving this property that are related to tree-like decompositions. We also provide an unified presentation of the current state of the art on this topic.

Citations

• A tight Erdős-Pósa function for long cycles
• �ber die Maximalzahl kreuzungsfreierH-Wege
• Polynomial Gap Extensions of the Erdős-Pósa Theorem

Cited by

• An Induced A-Path Theorem
• The Erdős-Pósa property for prime-length cycles fails (and beyond)
• Tree decompositions with small width, spread, order and degree
• On the Erdős-Pósa property for long holes in C₄-free graphs

Related

• Packing and covering induced subdivisions
• Improved Erdős-Pósa inequalities for odd cycles in planar graphs
• Obstructions to Erdős-Pósa Dualities for Minors
• An O(log OPT)-approximation for covering and packing minor models of θ_r
• Polynomial Gap Extensions of the Erdős-Pósa Theorem