Hanauer's feedback arc set conjecture for degree-five oriented multigraphs
Hanauer's feedback arc set conjecture for degree-five oriented multigraphs
Let be an oriented multigraph, and write for its maximum degree. A feedback arc set is a set of arcs whose deletion makes acyclic; let denote its minimum size. Let be the number of vertices.
Hanauer's conjecture. If , then
Hanauer posed this as a bounded-degree upper bound for the minimum feedback arc set. The conjecture is solved by the paper's main theorem, which establishes the stronger estimate ; since implies , the conjectured bound follows.
Sources & referencesView supporting material
Primary source
Gregory Gutin, Hui Lei, Anders Yeo and Yacong Zhou, “Upper bounds on minimum size of feedback arc set of directed multigraphs with bounded degree”, arXiv:2409.07680 (2024).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.