A well-quasi-order for tournaments

被引：21

作者：

Chudnovsky, Maria ^{[1
]}

Seymour, Paul ^{[2
]}

机构：

[1] Columbia Univ, New York, NY 10027 USA

[2] Princeton Univ, Princeton, NJ 08544 USA

来源：

JOURNAL OF COMBINATORIAL THEORY SERIES B | 2011年 / 101卷 / 01期

关键词：

Well-quasi-order; Digraph; Tournament; Immersion; Minor;

D O I：

10.1016/j.jctb.2010.10.003

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

A digraph H is immersed in a digraph G if the vertices of H are mapped to (distinct) vertices of G, and the edges of H are mapped to directed paths joining the corresponding pairs of vertices of G, in such a way that the paths are pairwise edge-disjoint. For graphs the same relation (using paths instead of directed paths) is a well-quasi-order: that is, in every infinite set of graphs some one of them is immersed in some other. The same is not true for digraphs in general: but we show it is true for tournaments (a tournament is a directed complete graph). (C) 2010 Published by Elsevier Inc.

引用

页码：47 / 53

页数：7

共 7 条

[1]

CHUDNOVSKY M, 2009, TOURNAMENT IMM UNPUB

[2]

CHUDNOVSKY M, PROOF RAOS DEG UNPUB

[3]

Higman G., 1952, Proc. London Math. Soc., V2, P326

[4]

Johnson T, 2002, THESIS PRINCETON U