Partition conjecture for strengthening sets of a crossing family

Let D=(V,A)D=(V,A) be a weakly connected digraph, let C\mathcal{C} be a crossing family over VV, and let a strengthening set of DD for C\mathcal{C} be a subset JAJ\subseteq A such that every set in C\mathcal{C} has at least one outgoing arc after the arcs in JJ are flipped. Let τ2\tau\geq2 be an integer.

Strengthening-set partition conjecture. If

δD(U)+(τ1)δD+(U)τ|\delta_D^-(U)|+(\tau-1)|\delta_D^+(U)|\geq\tau

for every UCU\in\mathcal{C}, then AA can be partitioned into τ\tau strengthening sets of DD for C\mathcal{C}.

The conjecture unifies several directed-cut partition statements: for τ=2\tau=2 it is equivalent to the paper's strong-orientation theorem, and a suitable choice of C\mathcal{C} yields Woodall's conjecture. Its validity in the general crossing-family setting remains open.

Sources & referencesView supporting material

Primary source

Ahmad Abdi, Mahsa Dalirrooyfard and Meike Neuwohner, “Strong orientation of a connected graph for a crossing family”, arXiv:2411.13202 (2024).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.