The MathNet Korea
Information Center for Mathematical Science

세미나

Information Center for Mathematical Science

세미나

KAIST Discrete Math 세미나
Title A tight Erdős-Pósa function for planar minors
Date 2018-12-10
Speaker Tony Huynh(Université libre de Bruxelles)
Sponsors 2018-12-10
Host KAIST
Place Room A209, IBS
Abstract Let H be a planar graph. By a classical result of Robertson and Seymour, there is a function f(k) such that for all k and all graphs G, either G contains k vertex-disjoint subgraphs each containing H as a minor, or there is a subset X of at most f(k) vertices such that G−X has no H-minor. We prove that this remains true with f(k)=ck log k for some constant c depending on H. This bound is best possible, up to the value of c, and improves upon a recent bound of Chekuri and Chuzhoy. The proof is constructive and yields the first polynomial-time O(log