zbMATH — the first resource for mathematics

A well-quasi-order for tournaments. (English) Zbl 1221.05178
Summary: 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).

05C20 Directed graphs (digraphs), tournaments
Full Text: DOI
[1] Maria Chudnovsky, Alexandra Fradkin, Paul Seymour, Tournament immersion and cutwidth, manuscript, June 2009, submitted for publication. · Zbl 1241.05040
[2] Maria Chudnovsky, Paul Seymour, A proof of Rao’s degree sequence conjecture, in preparation. · Zbl 1300.05065
[3] Higman, G., Ordering by divisibility in abstract algebras, Proc. London math. soc. (3), 2, 326-336, (1952) · Zbl 0047.03402
[4] Thor Johnson, Eulerian Digraph Immersion, PhD thesis, Princeton University, 2002.
[5] Kriz, Igor, Well-quasiordering finite trees with gap-condition. proof of harvey Friedman’s conjecture, Ann. of math., 130, 215-226, (1989) · Zbl 0684.05016
[6] Robertson, Neil; Seymour, Paul, Graph minors. XX. Wagner’s conjecture, J. combin. theory ser. B, 92, 325-357, (2004) · Zbl 1061.05088
[7] Robertson, Neil; Seymour, Paul, Graph minors. XXIII. Nash-Williams’s immersion conjecture, J. combin. theory ser. B, 100, 181-205, (2010) · Zbl 1216.05151
[8] Simpson, S.G., Nonprovability of certain combinatorial properties of finite trees, (), 87-117
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.