ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let M=(V,E∪A)M=(V,E\cup A) be a mixed graph, where AA is the set of directed arcs and EE the set of undirected edges. For U⊂VU\subset V, a pseudo dicut is the edge set δE(U)\delta_E(U) such that no directed arc enters UU. An orientation E+E^+ of EE replaces every undirected edge by a directed edge. For an oriented cut, write δE++(U)\delta_{E^+}^+(U) and δE+−(U)\delta_{E^+}^-(U) for its outgoing and incoming edges.

Mixed-graph orientation conjecture. There is a constant k>2k>2 such that for every mixed graph M=(V,E∪A)M=(V,E\cup A), there is an orientation E+E^+ such that

∣δE++(U)∣,∣δE+−(U)∣≥⌊1k∣δE(U)∣⌋|\delta_{E^+}^+(U)|,|\delta_{E^+}^-(U)|\geq \left\lfloor\frac{1}{k}|\delta_E(U)|\right\rfloor

for every pseudo dicut δE(U)\delta_E(U).

This is proposed as an analogue of nowhere-zero flow methods for mixed graphs. The source notes that the counterexample to Edmonds–Giles implies k>2k>2, 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 in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.