Coloring the edges of a directed graph

Finding large cliques in a graph is an important problem in applied discrete mathematics. In directed graph a possible corresponding problem is finding large transitive subtournaments. It is well-known that coloring the graph speeds up the clique search in the undirected case. In this paper we propose coloring schemes to speed up the tournament search in the directed case. We prove two complexity results about the proposed colorings. A consequence of these results is that in practical computations we have to be content with approximate greedy coloring algorithms.