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

Jean Florent Raymond; Dimitrios M. Thilikos

doi:10.1016/j.dam.2016.12.025

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

Jean Florent Raymond, Dimitrios M. Thilikos

Computer Science

Research output: Contribution to journal › Article › peer-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 language	English (US)
Pages (from-to)	25-43
Number of pages	19
Journal	Discrete Applied Mathematics
Volume	231
DOIs	https://doi.org/10.1016/j.dam.2016.12.025
State	Published - Nov 20 2017

Keywords

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

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Access to Document

10.1016/j.dam.2016.12.025

Cite this

@article{e1e354b9ca234a649345b9e2a1cf9dff,

title = "Recent techniques and results on the Erd{\H o}s–P{\'o}sa property",

abstract = "Several min–max relations in graph theory can be expressed in the framework of the Erd{\H o}s–P{\'o}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.",

keywords = "Erd{\H o}s–P{\'o}sa property, Girth, Graph immersions, Graph minors, Topological minors, Tree decompositions, Tree partitions, min–max theorems",

author = "Raymond, {Jean Florent} and Thilikos, {Dimitrios M.}",

note = "Publisher Copyright: {\textcopyright} 2017 Elsevier B.V.",

year = "2017",

month = nov,

day = "20",

doi = "10.1016/j.dam.2016.12.025",

language = "English (US)",

volume = "231",

pages = "25--43",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

}

TY - JOUR

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

AU - Raymond, Jean Florent

AU - Thilikos, Dimitrios M.

PY - 2017/11/20

Y1 - 2017/11/20

N2 - 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.

AB - 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.

KW - Erdős–Pósa property

KW - Girth

KW - Graph immersions

KW - Graph minors

KW - Topological minors

KW - Tree decompositions

KW - Tree partitions

KW - min–max theorems

UR - http://www.scopus.com/inward/record.url?scp=85012888890&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85012888890&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2016.12.025

DO - 10.1016/j.dam.2016.12.025

M3 - Article

AN - SCOPUS:85012888890

SN - 0166-218X

VL - 231

SP - 25

EP - 43

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -

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

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this