On the Erdos-Hajnal conjecture for six-vertex tournaments

A celebrated unresolved conjecture of Erdos and Hajnal states that for every undirected graph H there exists (H) > 0 such that every undirected graph on n vertices that does not contain H as an induced subgraph contains a clique or stable set of size at least n(H). The conjecture has a directed equivalent version stating that for every tournament H there exists (H) > 0 such that every H-free n-vertex tournament T contains a transitive subtournament of order at least n(H). We say that a tournament is prime if it does not have nontrivial homogeneous sets. So far the conjecture was proved only for some specific families of prime tournaments and tournaments constructed according to the so-called substitution procedure. In particular, recently the conjecture was proved for all five-vertex tournaments, but the question about the correctness of the conjecture for all six vertex tournaments remained open. In this paper we prove that all but at most one six vertex tournament satisfy the Erdos-Hajnal conjecture. That reduces the six-vertex case to a single tournament.

• Algorithms and Theory