Hanauer et al.'s feedback arc set conjecture for strongly connected degree-five oriented graphs
Hanauer et al.'s feedback arc set conjecture for strongly connected degree-five oriented graphs
Let be a strongly connected oriented graph, and let denote 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 et al.'s conjecture. If , then
This is a stronger-looking bound for strongly connected oriented graphs than the general degree-five multigraph conjecture. The supplied excerpt does not state whether this conjecture has been resolved, so its database status remains open.
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
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).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.