A well-quasi-order for tournaments

作者：Chudnovsky Maria^*; Seymour Paul

来源：Journal of Combinatorial Theory - Series B, 2011, 101(1): 47-53.

DOI：10.1016/j.jctb.2010.10.003

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

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).

• 出版日期2011-1