caa a22 4500 445358440 CHVBK 20180317142908.0 cr unu---uuuuu 170323e20110101xx s 000 0 eng 10.1007/s00493-011-2589-4 doi (NATIONALLICENCE)springer-10.1007/s00493-011-2589-4 Destroying cycles in digraphs [Elektronische Daten] [Molly Dunkum, Peter Hamburger, Attila Pór] For a simple directed graph G with no directed triangles, let β(G) be the size of the smallest subset X ∈ E(G) such that G\X has no directed cycles, and let γ(G) denote the number of unordered pairs of nonadjacent vertices in G. Chudnovsky, Seymour, and Sullivan showed that β(G) ≤ γ(G), and conjectured that β(G) ≤ $\tfrac{{\gamma (G)}} {2}$ . In this paper we prove that β(G)<0.88γ(G). János Bolyai Mathematical Society and Springer Verlag, 2011 Dunkum Molly Department of Mathematics and Computer Science, Western Kentucky University, 42101, Bowling Green, KY, USA aut Hamburger Peter Department of Mathematics and Computer Science, Western Kentucky University, 42101, Bowling Green, KY, USA aut Pór Attila Department of Mathematics and Computer Science, Western Kentucky University, 42101, Bowling Green, KY, USA aut Combinatorica Springer-Verlag 31/1(2011-01-01), 55-66 0209-9683 31:1<55 2011 31 493 https://doi.org/10.1007/s00493-011-2589-4 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00493-011-2589-4 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Dunkum Molly Department of Mathematics and Computer Science, Western Kentucky University, 42101, Bowling Green, KY, USA aut NATIONALLICENCE 700 1- Hamburger Peter Department of Mathematics and Computer Science, Western Kentucky University, 42101, Bowling Green, KY, USA aut NATIONALLICENCE 700 1- Pór Attila Department of Mathematics and Computer Science, Western Kentucky University, 42101, Bowling Green, KY, USA aut NATIONALLICENCE 773 0- Combinatorica Springer-Verlag 31/1(2011-01-01), 55-66 0209-9683 31:1<55 2011 31 493 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer