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

About 6 years old · traced to

Let m≥3m\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)(m−2)γ(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.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.