Mixed-graph pseudo-dicut orientation conjecture
Statement
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.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.