Optimally large cuts in both directions

Frederic Folz, Mykhaylo Tyomkyn

We prove that for every integer $d\ge 2$ and all sufficiently large $m$, every digraph with $m$ edges and minimum outdegree at least $d$ has a vertex bipartition for which each dire…