×

Structure theorem for \(U_{5}\)-free tournaments. (English) Zbl 1314.05087

Let \(U_{5}\) be the tournament with vertices \(v_{1},\dots,v_5\) such that there is a directed edge from \(v_{2}\) to \(v_{1}\) and from \(v_{i}\) to \(v_{j}\) if \(j-i\) is congruent to \(1,2 \pmod{5}\) and \(\{i,j\}\) is not equal to \(\{1,2\}\). Here the author describes all tournaments that have not \(U_{5}\) as a subtournament by constructing all \(U_{5}\)-free tournaments. He also proofs that all \(U_{5}\)-free tournaments with \(n\) vertices has a transitive subtournament with at least \(n^{\log_32}\) vertices.

MSC:

05C20 Directed graphs (digraphs), tournaments
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Alon, Ramsey-type theorems with forbidden subgraphs, Combinatorica 21 pp 155– (2001) · Zbl 0989.05124 · doi:10.1007/s004930100016
[2] Belkhechine, Indecomposable tournaments and their indecomposable subtournaments on 5 and 7 vertices, Ars Combin 108 pp 493– (2013) · Zbl 1107.05041
[3] E. Berger K. Choromanski M. Chudnovsky Forcing large transitive subtournaments 2012 · Zbl 1310.05106
[4] Berger, Tournaments and colouring, J Combin Theory Ser B 103 pp 1– (2013) · Zbl 1254.05064 · doi:10.1016/j.jctb.2012.08.003
[5] Boudabbous, Indecomposability graph and critical vertices of an indecomposable graph, Disc Math 309 pp 2839– (2009) · Zbl 1182.05062 · doi:10.1016/j.disc.2008.07.015
[6] K. Choromanski M. Chudnovsky P. Seymour Tournaments with near-linear transitive subsets 2012 · Zbl 1301.05145
[7] Chudnovsky, Growing without cloning, SIAM J Discrete Math 26 pp 860– (2012) · Zbl 1248.05170 · doi:10.1137/100817255
[8] Ehrenfeucht, Primitivity is hereditary for 2-structures, Theoret Comput Sci 70 pp 343– (1990) · Zbl 0701.05053 · doi:10.1016/0304-3975(90)90131-Z
[9] Latka, Structure theorem for tournaments omitting N5, J Graph Theory 42 pp 165– (2003) · Zbl 1016.05036 · doi:10.1002/jgt.10081
[10] G. Liu Various Theorems on Tournaments 2012
[11] Schmerl, Critically indecomposable partially ordered sets, graphs, tournaments, and other binary relational structures, Discrete Math 113 pp 191– (1993) · Zbl 0776.06002
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.