Judicious partitioning problems on graphs ask for partitions that bound several quantities simultaneously, which have received a lot of attentions lately. Scott asked the following natural question: What is the maximum constant such that every directed graph with arcs and minimum outdegree admits a bipartition satisfying $\min{e(V_1, V_2), e(V_2, V_1)}\ge c_d mi=1,2e(V_{i},V_{3-i})$ denotes the number of arcs in from to . Lee, Loh, and Sudakov %[Judicious partitions of directed graphs, Random Struct. Alg. 48 %(2016) 147–170] conjectured that every directed graph with arcs and minimum outdegree at least admits a bipartition such that %While it is not known whether or not the minimum outdegree condition %alone is sufficient, w We show that this conjecture holds under the additional natural condition that the minimum indegree is also at least .

生成讲解博客的中文版本

生成AI智能校验的中文版本