摘要
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)=V_1∪V_2 satisfying min{e(V_1,V_2),e(V_2,V_1)}cdm?Here,for i=1,2,e(V_i,V_(3-i))denotes the number of arcs in D from V_i to V_(3-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)=V_1∪V_2 such that min{e(V_1,V_2),e(V_2,V_1)}≥((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.
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.
基金
supported by National Natural Science Foundation of China (Grant No. 11671087)
supported by National Science Foundation of USA (Grant No. DMS1600738)
the Hundred Talents Program of Fujian Province
supported by the Shandong Provincial Natural Science Foundation of China (Grant No. ZR2014JL001)
the Excellent Young Scholars Research Fund of Shandong Normal University of China
