Destroying cycles in digraphs (Q653984): Difference between revisions

Every 3-free tournament is acyclic. The present paper investigates the following question: If a simple 3-free digraph is obtained from a tournament by deleting \(k\) edges, what is the minimum number of additional edges that must be deleted in order to obtain an acyclic digraph? The result improves some earlier upper bounds by other researchers (\textit{M. Chudnovsky, P. Seymour} and \textit{B. Sullivan} [Combinatorica 28, 1--18 (2008; Zbl 1174.05049)], \textit{P. Hamburger, P. Haxell} and \textit{A. Kostochka} [Electron. J. Comb. 14, No. 1, Research Paper N19 (2007; Zbl 1157.05311)]) but does not prove the conjecture that each \(n\)-vertex digraph with minimum outdegree at least \(n/3\) contains a directed triangle (\textit{L. Caccetta} and \textit{R. Häggkvist} [Congressus Numerantium XXI, 181--187 (1978; Zbl 0406.05033)]).