CNRS, LIRMM, Montpellier
Title
On the Erdős–Pósa property for minors of graphs
Abstract
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 G ∖ S 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.
