CNRS, LIRMM, Montpellier



On the Erdős–Pósa property for minors of graphs


A class of graphs C satisfies the Erdős–Pósa property if there exists a function fC such that, for every integer k and every graph G, either G contains k vertex-disjoint subgraphs each isomorphic to a graph in C, or there is a subset S of V(G) of at most fC(k) vertices such that GS has no subgraph in C. Erdős and Pósa (1965) proved that the set of all cycles satisfies this property with f(k) = O(k log k). Given a connected graph H, let M(H) be the class of graphs that contain H as a minor. Robertson and Seymour (1986) proved that M(H) satisfies the Erdős-Pósa property if and only if H is planar. When H is planar, finding the smallest possible function fM(H) has been an active area of research in the last years. In this talk we will survey some recent results in this direction, and we will discuss other variants of the Erdős–Pósa property such as the case where the k subgraphs have to be edge-disjoint or the case where M(H) is the class of graphs that contain a graph H as a topological minor.

We will mention results arising from joint work with Dimitris Chatzidimitriou, Samuel Fiorini, Gwenaël Joret, Jean-Florent Raymond, and Dimitrios M. Thilikos.


The Catalan Mathematical Society invites participants to this first congress of a biannual series focusing on current research topics across several areas of Mathematics.

Plenary talks and thematic sessions have been selected by the Scientific Committee of the SCM. Special thanks are due to the organisers of the thematic sessions and to the local mathematical community as a whole for their support to this congress.


Societat Catalana de Matemàtiques
Institut d'Estudis Catalans
Carrer del Carme, 47
08001 Barcelona

Phone: +34 933 248 583

Download a poster (high res)

Download a poster (low res)