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

Jean Florent Raymond, Dimitrios M. Thilikos

Research output: Contribution to journalArticlepeer-review

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.

Original languageEnglish (US)
Pages (from-to)25-43
Number of pages19
JournalDiscrete Applied Mathematics
Volume231
DOIs
StatePublished - Nov 20 2017

Keywords

  • Erdős–Pósa property
  • Girth
  • Graph immersions
  • Graph minors
  • min–max theorems
  • Topological minors
  • Tree decompositions
  • Tree partitions

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Recent techniques and results on the Erdős–Pósa property'. Together they form a unique fingerprint.

Cite this