Hanauer et al.'s feedback arc set conjecture for strongly connected degree-five oriented graphs

From papers

Let DD be a strongly connected oriented graph, and let Δ\Delta denote its maximum degree. A feedback arc set is a set of arcs whose deletion makes DD acyclic; let fas(D){\rm fas}(D) denote its minimum size. Let nn be the number of vertices.

Hanauer et al.'s conjecture. If Δ5\Delta\leq 5, then

fas(D)2n3.{\rm fas}(D)\leq \frac{2n}{3}.

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

No solutions have been posted yet.