Strong immersion is a well-quasi-ordering for semicomplete digraphs

被引：2

作者：

Barbero, Florian ^{[1
]}

Paul, Christophe ^{[1
]}

Pilipczuk, Michal ^{[2
]}

机构：

[1] Univ Montpellier, CNRS, LIRMM, F-34095 Montpellier, France

[2] Univ Warsaw, MIMUW, Warsaw, Poland

来源：

JOURNAL OF GRAPH THEORY | 2019年 / 90卷 / 04期

关键词：

immersion order; semicomplete digraphs; well-quasi-ordering;

D O I：

10.1002/jgt.22408

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We prove that the strong immersion order is a well-quasi-ordering on the class of semicomplete digraphs, thereby strengthening a result of Chudnovsky and Seymour (2011, J. Comb. Theory, Series B, 101, 47-53) that this holds for the class of tournaments.

引用

页码：484 / 496

页数：13

共 19 条

[1] Tournament immersion and cutwidth [J].

Chudnovsky, Maria ;

Fradkin, Alexandra ;

Seymour, Paul .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 2012, 102 (01) :93-101

[2] A well-quasi-order for tournaments [J].

Chudnovsky, Maria ;

Seymour, Paul .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 2011, 101 (01) :47-53

[3]

Cygan Marek., 2014, PARAMETERIZED ALGORI

[4]

Downey R., 2013, TEXT COMPUTER SCI

[5]

Flum J., 2006, Parameterized Complexity Theory

[6]

Giannopoulou A., 2017, INT C AUT LANG PROGR, V80

[7]

Grohe M, 2011, ACM S THEORY COMPUT, P479

[8]

Kawarabayashi K., 2014, SODA, P72

[9] An FPT 2-Approximation for Tree-cut Decomposition [J].

Kim, Eunjung ;

Oum, Sang-il ;

Paul, Christophe ;

Sau, Ignasi ;

Thilikos, Dimitrios M. .

APPROXIMATION AND ONLINE ALGORITHMS, WAOA 2015, 2015, 9499 :35-46

[10] Tournament minors [J].

Kim, Ilhee ;

Seymour, Paul .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 2015, 112 :138-153

← 1 2 →