Back to Search
Start Over
Recent techniques and results on the Erdős-Pósa property
- Source :
- Discrete Applied Mathematics, Discrete Applied Mathematics, Elsevier, 2017, 231, pp.25-43. 〈10.1016/j.dam.2016.12.025〉, Discrete Applied Mathematics, Elsevier, 2017, 231, pp.25-43. ⟨10.1016/j.dam.2016.12.025⟩
- Publication Year :
- 2017
- Publisher :
- HAL CCSD, 2017.
-
Abstract
- International audience; 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.
- Subjects :
- Current (mathematics)
Property (philosophy)
tree partitions
G.2.1
G.2.2
0102 computer and information sciences
[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
[ MATH.MATH-CO ] Mathematics [math]/Combinatorics [math.CO]
01 natural sciences
girth
min-max theorems
[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
Mathematics - Combinatorics
Discrete Mathematics and Combinatorics
Erdős–Pósa property
0101 mathematics
tree decompositions
graph minors
Mathematics
Discrete mathematics
Erd˝ os–Pósa property
graph immersions
05C70
Applied Mathematics
010102 general mathematics
Covering problems
Graph theory
[ INFO.INFO-DM ] Computer Science [cs]/Discrete Mathematics [cs.DM]
State (functional analysis)
Girth (graph theory)
16. Peace & justice
Connection (mathematics)
010201 computation theory & mathematics
topological minors
min–max theorems
MathematicsofComputing_DISCRETEMATHEMATICS
Computer Science - Discrete Mathematics
Subjects
Details
- Language :
- English
- ISSN :
- 0166218X
- Database :
- OpenAIRE
- Journal :
- Discrete Applied Mathematics, Discrete Applied Mathematics, Elsevier, 2017, 231, pp.25-43. 〈10.1016/j.dam.2016.12.025〉, Discrete Applied Mathematics, Elsevier, 2017, 231, pp.25-43. ⟨10.1016/j.dam.2016.12.025⟩
- Accession number :
- edsair.doi.dedup.....2d06d2ef489c5a34ee82b9fe569e6ba6
- Full Text :
- https://doi.org/10.1016/j.dam.2016.12.025〉