KAIST Discrete Math Seminar

A set F of graphs has the Erdős-Posa property if there exists a function f such that every graph either contains k disjoint subgraphs each isomorphic to a member in F or contains a set of at most f(k) vertices intersecting all such subgraphs. In this talk I will address the Erdős-Posa property with respect to three closely related graph containment relations: minor, topological minor, and immersion. We denote the set of graphs containing H as a minor, topological minor and immersion by M(H),T(H) and I(H), respectively. Robertson and Seymour in 1980’s proved that M(H) has the Erdős-Posa property if and only if H is planar. And they left the question for characterizing H in which T(H) has the Erdős-Posa property in the same paper. This characterization is expected to be complicated as T(H) has no Erdős-Posa property even for some tree H. In this talk, I will present joint work with Postle and Wollan for providing such a characterization. For immersions, it is more reasonable to consider an edge-variant of the Erdős-Posa property: packing edge-disjoint subgraphs and covering them by edges. I(H) has no this edge-variant of the Erdős-Posa property even for some tree H. However, I will prove that I(H) has the edge-variant of the Erdős-Posa property for every graph H if the host graphs are restricted to be 4-edge-connected. The 4-edge-connectivity cannot be replaced by the 3-edge-connectivity.