On dijoins (Q5957710): Difference between revisions

For a digraph \(D\), a dicut is a non-empty set of arcs of the form \(\{(u, v):u\in U,v\not\in U\}\) such that there is no arc \((u,v)\) with \(v\in U\) and \(u\not\in\overline U\). A dijoin is a set of arcs that intersects every dicut. In 1977, \textit{J. Edmonds} and \textit{R. Giles} [Ann. Discrete Math. 1, 185-204 (1977; Zbl 0373.05040)] conjectured that for every nonnegative integer arc weight function \(w\), the minimum weight of a dicut is equal to the maximum number of dijoins such that no arc \(a\) is contained in more than \(w(a)\) of these dijoins. In 1980, \textit{A. Schrijver} [Discrete Math. 32, 213-214 (1980; Zbl 0445.05047)] obtained a counterexample to this conjecture. The present authors exhibit two other counterexamples and discuss the possibility that the three counterexamples are the only ``minimal'' ones.