Unavoidable Subtournaments in Large Tournaments with No Homogeneous Sets
2017
A loopless digraph is a tournament if for every pair of distinct vertices $u$ and $v$, exactly one of $uv$ and $vu$ is an edge. For a tournament $T$, a set $S\subseteq V(T)$ is homogeneous if every vertex $v$ outside of $S$ is either complete to $S$ or complete from $S$. A tournament is prime if for every homogeneous set $S$ of $T$, either $|S| \le 1$ or $S=V(T)$. In this paper, we present a list of eight classes of prime tournaments and prove that for every positive integer $n$, there exists $N$ such that every prime tournament of size at least $N$ contains a prime tournaments from the list of size at least $n$.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
0
References
1
Citations
NaN
KQI