◈ 학술지
◈ 도서
◈ 전자학술지
◈ 투고요령
◈ 수학신간도서
◈ MSC
◈ 논문검색
◈ 학술행사
홈 > 학술정보 >학술행사 > 세미나
KAIST Discrete Math 세미나

Title
A tight Erdős-Pósa function for planar minors
Speaker
Tony Huynh   (Université libre de Bruxelles )
Date
2018-12-10 17:00:00
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
개인정보보호정책 l 이메일주소집단수집금지 l 뷰어다운로드
qr코드