  Coloring graphs is an important algorithmic problem in combinatorics with
many applications in computer science. In this paper we study coloring
tournaments. A chromatic number of a random tournament is of order
$\Omega(\frac{n}{\log(n)})$. The question arises whether the chromatic number
can be proven to be smaller for more structured nontrivial classes of
tournaments. We analyze the class of tournaments defined by a forbidden
subtournament $H$. This paper gives a first quasi-polynomial algorithm running
in time $e^{O(\log(n)^{2})}$ that constructs colorings of $H$-free tournaments
using only $O(n^{1-\epsilon(H)}\log(n))$ colors, where $\epsilon(H) \geq
2^{-2^{50|H|^{2}+1}}$ for many forbidden tournaments $H$. To the best of our
knowledge all previously known related results required at least
sub-exponential time and relied on the regularity lemma. Since we do not use
the regularity lemma, we obtain the first known lower bounds on $\epsilon(H)$
that can be given by a closed-form expression. As a corollary, we give a
constructive proof of the celebrated open Erd\H{o}s-Hajnal conjecture with
explicitly given lower bounds on the EH coefficients for all classes of prime
tournaments for which the conjecture is known. Such a constractive proof was
not known before. Thus we significantly reduce the gap between best lower and
upper bounds on the EH coefficients from the conjecture for all known prime
tournaments that satisfy it. We also briefly explain how our methods may be
used for coloring $H$-free tournaments under the following conditions: $H$ is
any tournament with $\leq 5$ vertices or: $H$ is any but one tournament of six
vertices.
