Sullivan's conjecture on feedback arc sets in m-free digraphs
Sullivan's conjecture on feedback arc sets in m-free digraphs
Let , and let be an -free digraph, meaning that has no directed cycle of length at most . Let be the minimum number of edges whose removal makes acyclic, and let be the number of unordered pairs of nonadjacent vertices of . Sullivan's conjecture.
Sullivan proposed this as a best-possible general bound. The paper states related results for several values of , 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
Sign in to submit a solution.
No solutions have been posted yet.