Structure Theorem forU5-free Tournaments
Gaku Liu · Journal of Graph Theory · 2014
Let U5 be the tournament with vertices v1, …, v5 such that , and if , and . In this article, we describe the tournaments that do not have U5 as a subtournament. Specifically, we show that if a tournament G is “prime”—that is, if there is no subset , , such that for all , either for all or for all —then G is U5-free if and only if either G is a specific tournament or can be partitioned into sets X, Y, Z such that , , and are transitive. From the prime U5-free tournaments we can construct all the U5-free tournaments. We use the theorem to show that every U5-free tournament with n vertices has a transitive subtournament with at least vertices, and that this bound is tight.