Sullivan's conjecture on feedback arc sets in m-free digraphs

From papers

Let m3m\ge 3, and let GG be an mm-free digraph, meaning that GG has no directed cycle of length at most mm. Let β(G)\beta(G) be the minimum number of edges whose removal makes GG acyclic, and let γ(G)\gamma(G) be the number of unordered pairs of nonadjacent vertices of GG. Sullivan's conjecture.

β(G)2(m+1)(m2)γ(G).\beta(G)\le \frac{2}{(m+1)(m-2)}\gamma(G).

Sullivan proposed this as a best-possible general bound. The paper states related results for several values of mm, but does not report a resolution of the general conjecture.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Dan Ismailescu, Joonsoo Lee and Andrew Yang, “Outdegree conditions forcing short cycles in digraphs”, arXiv:2008.09171 (2020).

Solutions 0

No solutions have been posted yet.