Partition conjecture for strengthening sets of a crossing family

About 2 years old · traced to

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 J⊆AJ\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 U∈CU\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.

References

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.