On the Erdos-Posa property for immersions and topological minors in tournaments

被引:0
作者
Bozyk, Lukasz [1 ]
Pilipczuk, Michal [1 ]
机构
[1] Univ Warsaw, Inst Informat, Warsaw, Poland
基金
欧盟地平线“2020”; 欧洲研究理事会;
关键词
directed Erdos-Posa property; packing and covering; immersions; topological minors; tournaments;
D O I
10.46298/dmtcs.7099
中图分类号
TP31 [计算机软件];
学科分类号
081202 ; 0835 ;
摘要
We consider the Erdos-Posa property for immersions and topological minors in tournaments. We prove that for every simple digraph H, k is an element of N, and tournament T, the following statements hold: If in T one cannot find k arc-disjoint immersion copies of H, then there exists a set of O-H(k(3)) arcs that intersects all immersion copies of H in T. If in T one cannot find k vertex-disjoint topological minor copies of H, then there exists a set of O-H(k log k) vertices that intersects all topological minor copies of H in T. This improves the results of Raymond [DMTCS '18], who proved similar statements under the assumption that H is strongly connected.
引用
收藏
页数:16
相关论文
共 13 条
[1]  
Amiri S.A., 2016, ABS160302504 CORR
[2]  
Bessy S., 2019, LIPICS, V138
[3]   Tournament immersion and cutwidth [J].
Chudnovsky, Maria ;
Fradkin, Alexandra ;
Seymour, Paul .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2012, 102 (01) :93-101
[4]   ON INDEPENDENT CIRCUITS CONTAINED IN A GRAPH [J].
ERDOS, P ;
POSA, L .
CANADIAN JOURNAL OF MATHEMATICS, 1965, 17 (02) :347-&
[5]  
Erdos P., 1963, Publ. Math. (Debr.), V10, P10
[6]   On width measures and topological problems on semi-complete digraphs [J].
Fomin, Fedor, V ;
Pilipczuk, Michal .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2019, 138 :78-165
[7]   Strengthening Erdos-Posa Property for Minor-Closed Graph Classes [J].
Fomin, Fedor V. ;
Saurabh, Saket ;
Thilikos, Dimitrios M. .
JOURNAL OF GRAPH THEORY, 2011, 66 (03) :235-240
[8]   Tournament pathwidth and topological containment [J].
Fradkin, Alexandra ;
Seymour, Paul .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2013, 103 (03) :374-384
[9]  
Raymond J.-F., Dynamic Erdos-Posa listing
[10]  
Raymond JF, 2018, DISCRETE MATH THEOR, V20