  A $k$-coloring of a tournament is a partition of its vertices into $k$
acyclic sets. Deciding if a tournament is 2-colorable is NP-hard. A natural
problem, akin to that of coloring a 3-colorable graph with few colors, is to
color a 2-colorable tournament with few colors. This problem does not seem to
have been addressed before, although it is a special case of coloring a
2-colorable 3-uniform hypergraph with few colors, which is a well-studied
problem with super-constant lower bounds.
  We present an efficient decomposition lemma for tournaments and show that it
can be used to design polynomial-time algorithms to color various classes of
tournaments with few colors, including an algorithm to color a 2-colorable
tournament with ten colors. For the classes of tournaments considered, we
complement our upper bounds with strengthened lower bounds, painting a
comprehensive picture of the algorithmic and complexity aspects of coloring
tournaments.
