Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, April 14, 2015, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Andreas Noever
A family H of graphs is said to have the Erdős-Pósa property if there exists a function f: N -> N such that every graph G contains either k vertex-disjoint members of H or a set X of at most f(k) vertices such that G - X has no subgraph isomorphic to a graph in H. We show that, for every l, the family of circuits of length at least l satisfies the Erdős-Pósa property with f(k)=O(kl + k log k). This is optimal up to a constant factor. Joint work with Frank Mousset, Nemanja Skoric and Felix Weissenberger.
Automatic MiSe System Software Version 1.4803M | admin login