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.
References
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
No solutions have been posted yet.