Tournament minors

被引：17

作者：

Kim, Ilhee ^{[1
]}

Seymour, Paul ^{[1
]}

机构：

[1] Princeton Univ, Princeton, NJ 08540 USA

来源：

JOURNAL OF COMBINATORIAL THEORY SERIES B | 2015年 / 112卷

关键词：

Digraph; Tournament; Minor; Well-quasi-order; GRAPH MINORS;

D O I：

10.1016/j.jctb.2014.12.005

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We say a digraph G is a minor of a digraph H if G can be obtained from a subdigraph of H by repeatedly contracting a strongly-connected subdigraph to a vertex. Here, we show that the class of all tournaments is a well-quasi-order under minor containment. (C) 2014 Elsevier Inc. All rights reserved.

引用

页码：138 / 153

页数：16

共 50 条

[41] An approximation algorithm for the traveling tournament problem
Ryuhei Miyashiro
Tomomi Matsui
Shinji Imahori
Annals of Operations Research, 2012, 194 : 317 - 324
[42] Defective Coloring is Perfect for Minors
Liu, Chun-Hung
COMBINATORICA, 2024, 44 (03) : 467 - 507
[43] Hitting Topological Minors Is FPT
Fomin, Fedor, V
Lokshtanov, Daniel
Panolan, Fahad
Saurabh, Saket
Zehavi, Meirav
PROCEEDINGS OF THE 52ND ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING (STOC '20), 2020, : 1317 - 1326
[44] Genera and minors of multibranched surfaces
Matsuzaki, Ghosaku
Ozawa, Makoto
TOPOLOGY AND ITS APPLICATIONS, 2017, 230 : 621 - 638
[45] Compact Topological Minors in Graphs
Jiang, Tao
JOURNAL OF GRAPH THEORY, 2011, 67 (02) : 139 - 152
[46] A relationship between Minors and Linkages
Chen, Fuyuan
ARS COMBINATORIA, 2017, 133 : 317 - 327
[47] CUT DOMINANTS AND FORBIDDEN MINORS
Conforti, Michele
Fiorini, Samuel
Pashkovich, Kanstantsin
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2016, 30 (03) : 1571 - 1589
[48] Grid Minors in Damaged Grids
Eppstein, David
ELECTRONIC JOURNAL OF COMBINATORICS, 2014, 21 (03)
[49] A note on immersion minors and planarity
Wagner, Donald K.
DISCRETE MATHEMATICS, 2018, 341 (06) : 1605 - 1612
[50] An approximation algorithm for the traveling tournament problem
Miyashiro, Ryuhei
Matsui, Tomomi
Imahori, Shinji
ANNALS OF OPERATIONS RESEARCH, 2012, 194 (01) : 317 - 324

← 1 2 3 4 5 →