Loading Events

« All Events

  • This event has passed.

Tony Huynh, A tight Erdős-Pósa function for planar minors

Monday, December 10, 2018 @ 5:00 PM - 6:00 PM KST

Room B109, IBS

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 𝖮𝖯𝖳)-approximation algorithm for packing subgraphs containing an H-minor.

This is joint work with Wouter Cames van Batenburg, Gwenaël Joret, and Jean-Florent Raymond.


Monday, December 10, 2018
5:00 PM - 6:00 PM KST
Event Category:
Event Tags:


Room B109


Sang-il Oum (엄상일)
View Organizer Website
IBS 이산수학그룹 Discrete Mathematics Group
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209
Copyright © IBS 2018. All rights reserved.