Cookie Setting MathNet Korea

이전페이지 이동
Erdős-Pósa property of chordless cycles and its applications
[2018 Discrete Math 세미나]
Date: 2018-01-12
Speaker : O-joung Kwon (Technische Universität Berlin, Berlin, Germany)
Abstract : A chordless cycle in a graph G is an induced subgraph of G which is a cycle of length at least four. We prove that the Erdős-Pósa property holds for chordless cycles, which resolves the major open question concerning the Erdős-Pósa property. Our proof for chordless cycles is constructive: in polynomial time, one can find either k+1 vertex-disjoint chordless cycles, or ck2 log k vertices hitting every chordless cycle for some constant c. It immediately implies an approximation algorithm of factor O(OPT log OPT) for Chordal Vertex Deletion. We complement our main result by showing that chordless cycles of length at least ℓ for any fixed ℓ≥ 5 do not have the Erdős-Pósa property.
Information Center for Mathematical Sciences KAIST
34141 대전광역시 유성구 대학로 291 (구성동373-1)
한국과학기술원(KAIST) 수리과학정보센터
전화 042-350-8196
e-mail :
Copyright (C) 2018. ICMS All Rights Reserved.