Packing and covering topological minors and immersions

Graph Theory Seminar
Thursday, September 10, 2015 - 1:35pm
1 hour (actually 50 minutes)
Skiles 005
Princeton University
A set F of graphs has the Erdos-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 at most f(k) vertices
intersecting all such subgraphs. In this talk I will address the
Erdos-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 Erdos-Posa
property if and only if H is planar. And they left the question for
characterizing H in which T(H) has the Erdos-Posa property in the same
paper. This characterization is expected to be complicated as T(H) has
no Erdos-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 Erdos-Posa property: packing edge-disjoint subgraphs
and covering them by edges. I(H) has no this edge-variant of the
Erdos-Posa property even for some tree H. However, I will prove that
I(H) has the edge-variant of the Erdos-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.