The ACO Seminar (2016–2017)

A family F of graphs has the Erdős–Posa property if there exists a function f such that every graph either contains k disjoint subgraphs where each isomorphic to a member of F or contains a set of at most f(k) vertices intersecting all such subgraphs. The Erdős–Posa property describes the situation when the optimal solutions of the packing and covering problems can be bounded in terms of each others.

Erdős and Posa proved that the set of cycles has the Erdős–Posa property. This result was generalized by Robertson and Seymour in terms of graph minors. They proved that H is a graph such that the set of graphs containing H as a minor has the Erdős–Posa property if and only if H is planar. However, the Erdős–Posa property with respect to the topological minor containment is more subtle. I will present a complete characterization provided in joint work with Postle and Wollan for the graphs H in which the set of graphs containing H as a topological minor and answer a question of Robertson and Seymour. Our characterization is complicated, but a simple solution is unlikely to exist. I will also discuss how to avoid this complexity by considering other closely related containment relations.

Before the talk, at 3:10pm, there will be tea and cookies in Wean 6220.