| Abstract: | Judicious partitioning problems on graphs ask for partitions that bound several quantities simultaneously, which have received much attention lately. Scott（2005） asked the following natural question: What is the maximum constant cdsuch that every directed graph D with m arcs and minimum outdegree d admits a bipartition V（D） = V1 ∪ V2 satisfying min{e（V1, V2）, e（V2, V1）} cdm? Here, for i = 1, 2, e(Vi, V3-i) denotes the number of arcs in D from Vi to V3-i. Lee et al.（2016） conjectured that every directed graph D with m arcs and minimum outdegree at least d 2 admits a bipartition V（D） = V1 ∪ V2 such that min{e（V1, V2）, e（V2, V1）}≥（（d-1）/（2（2 d-1））+ o（1））m.In this paper, we show that this conjecture holds under the additional natural condition that the minimum indegree is also at least d. |
