| On the Chudnovsky-Seymour-Sullivan Conjecture on Cycles in Triangle-free Digraphs (2009) | |||||||||
Abstract | |||||||||
| For a simple digraph $G$ without directed triangles or digons, let $\beta(G)$ be the size of the smallest subset $X \subseteq E(G)$ such that $G\setminus X$ has no directed cycles, and let $\gamma(G)$ be the number of unordered pairs of nonadjacent vertices in $G$. In 2008, Chudnovsky, Seymour, and Sullivan showed that $\beta (G) \le \gamma(G)$, and conjectured that $\beta (G) \le \gamma(G)/2$. Recently, Dunkum, Hamburger, and P\'or proved that $\beta (G) \le 0.88 \gamma(G)$. In this note, we prove that $\beta (G) \le 0.8616 \gamma(G)$.. Comment: 5 pages | |||||||||
Publication details | |||||||||
| |||||||||