Conjectured value of the feedback arc set decomposition number for maximum degree 5 and directed girth 3

From papers

Let fasd(Δ,g){\rm fasd}(\Delta,g) denote the supremum, over the relevant weighted orgraphs of maximum degree at most Δ\Delta and directed girth at least gg, of the normalized feedback arc set decomposition parameter. The conjectured value.

fasd(5,3)=3.{\rm fasd}(5,3)=3.

The paper identifies this as the remaining case in its determination of fasd(Δ,3){\rm fasd}(\Delta,3) for Δ3\Delta\geq 3 and notes that proving it would generalize the established results fasd(4,3)=3{\rm fasd}(4,3)=3 and fas(5,3)=1/3{\rm fas}(5,3)=1/3 for the corresponding feedback arc parameter.

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, Mads Anker Nielsen, Anders Yeo and Yacong Zhou, “Feedback Arc Sets and Feedback Arc Set Decompositions in Weighted and Unweighted Oriented Graphs”, arXiv:2501.06935 (2025).

Solutions 0

No solutions have been posted yet.