Destroying cycles in digraphs
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)]).
scientific article; zbMATH DE number 5990942
scientific article