×

zbMATH — the first resource for mathematics

Tournament minors. (English) Zbl 1310.05109
Summary: 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.

MSC:
05C20 Directed graphs (digraphs), tournaments
05C83 Graph minors
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Chudnovsky, Maria; Seymour, Paul, A well-quasi-order for tournaments, J. Combin. Theory Ser. B, 101, 47-53, (2011) · Zbl 1221.05178
[2] Fradkin, Alexandra; Seymour, Paul, Tournament pathwidth and topological containment, J. Combin. Theory Ser. B, 103, 374-384, (2013) · Zbl 1301.05148
[3] Higman, G., Ordering by divisibility in abstract algebras, Proc. Lond. Math. Soc. (3), 2, 326-336, (1952) · Zbl 0047.03402
[4] Johnson, T.; Robertson, N.; Seymour, P.; Thomas, R., Directed treewidth, J. Combin. Theory Ser. B, 82, 128-154, (2001)
[5] Kreutzer, S.; Tazari, S., Directed nowhere dense classes of graphs, (Proc. 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA’12, (2012)), 1552-1562
[6] Robertson, N.; Seymour, P. D., Graph minors. I. excluding a forest, J. Combin. Theory Ser. B, 35, 39-61, (1983) · Zbl 0521.05062
[7] Robertson, N.; Seymour, P. D., Graph minors. XX. Wagner’s conjecture, J. Combin. Theory Ser. B, 92, 325-357, (2004) · Zbl 1061.05088
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.