Mixed-graph pseudo-dicut orientation conjecture
Mixed-graph pseudo-dicut orientation conjecture
Let be a mixed graph, where is the set of directed arcs and the set of undirected edges. For , a pseudo dicut is the edge set such that no directed arc enters . An orientation of replaces every undirected edge by a directed edge. For an oriented cut, write and for its outgoing and incoming edges.
Mixed-graph orientation conjecture. There is a constant such that for every mixed graph , there is an orientation such that
for every pseudo dicut .
This is proposed as an analogue of nowhere-zero flow methods for mixed graphs. The source notes that the counterexample to Edmonds–Giles implies , and gives no resolution.
Sources & referencesView supporting material
Primary source
Gérard Cornuéjols, Siyue Liu and R. Ravi, “Approximately Packing Dijoins via Nowhere-Zero Flows”, arXiv:2311.04337 (2025).
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
Sign in to submit a solution.
No solutions have been posted yet.