






홈 > 학술정보 >학술행사 > 세미나 





KAIST Discrete Math 세미나 



A tight ErdősPósa function for planar minors 

Tony Huynh (Université libre de Bruxelles ) 
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 vertexdisjoint 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 Hminor. 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 polynomialtime O(log 







