The Erdos-Posa property of H-minor models with prescribed vertex sets

O-joung Kwon (Hungarian Academy of Sciences)

When: Thursday November 19, 2pm

Where: room C417 (at the very end of the corridor)

Abstract

For a graph H, an H-expansion is a graph that can be contracted to H after removing some edges. A graph G contains an H-expansion if and only if H is a minor of G. A class C of graphs is said to have the Erdos-Posa property if for every k, there exists f(k,C) such that every graph contained either k vertex disjoint subgraphs in C, or there exists a vertex set of size at most f(k,C) that meets all subgraphs in C. Erdos and Posa (1965) originally showed that the class of all cycles has the Erdos-Posa property. Later, Robertson and Seymour (1986) proved that the class of all H-expansions has the Erdos-Posa property if and only if H is planar.

We generalize the result by Robertson and Seymour into H-expansions with some special property. Let Z_1, …, Z_m be vertex sets in a graph G, and let Z={Z_1, …, Z_m}. An H-expansion is called (Z, l)-intersecting if it intersects at least l sets of Z. For a pair of (H, l), does the class of (Z, l)-intersecting H-expansions have the Erdos-Posa property? If H is one vertex graph and l=2, then it follows from Mader’s S-path Theorem and if H is one vertex graph and l=3, then it does not hold.

We show that the class of (Z, l)-intersecting H-expansions has the Erdos-Posa property if and only if H is planar and it consists of at least l-1 component. For given k, we also design an FPT algorithm for finding either k disjoint (Z,l)-intersecting H-expansions or a vertex set of small size meeting all such expansions, where the parameters are k, l, |V(H)|. In this talk, I will slightly focus on how to use representative sets to achieve this FPT algorithm.

This is joint work with Dániel Marx.