Decomposing oriented graphs into transitive tournaments
If \(G\) is an oriented graph with \(n\) vertices, let \(f(G)\) denote the least number of arc-disjoint transitive subtournaments whose union includes all arcs of \(G\). The author shows that, in general, \(f(G)\leq\lfloor n^2/3\rfloor\) and that equality holds when \(G\) has at most \(n^2/3\) arcs. He also shows, among other things, that if \(G\) is a tournament, then \((n^2/3000)(1+ o(1))< f(G)< (5n^2/21)(1+ o(1))\).
scientific article; zbMATH DE number 5013289