On the Chudnovsky-Seymour-Sullivan Conjecture on Cycles in Triangle-free Digraphs

Abstract

For a simple digraph $G$ without directed triangles or digons, let ${\hat{I}}^2(G)$ be the size of the smallest subset $X\subseteq E(G)$ such that $G\setminus X$ has no directed cycles, and let ${\hat{I}}^3(G)$ be the number of unordered pairs of nonadjacent vertices in $G$. In 2008, Chudnovsky, Seymour, and Sullivan showed that ${\hat{I}}^2(G)\le {\hat{I}}^3(G)$, and conjectured that ${\hat{I}}^2(G)\le {\hat{I}}^3(G)/2$. Recently, Dunkum, Hamburger, and Pór proved that ${\hat{I}}^2(G)\le 0.88{\hat{I}}^3(G)$. In this note, we prove that ${\hat{I}}^2(G)\le 0.8616{\hat{I}}^3(G)$.

5 pages