Indexed by:
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 c(d) such 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, V1)} > c(d)m? Here, for i = 1, 2, e(V-i, V3-i) denotes the number of arcs in D from V-i 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) = V-1 ? V-2 such that minfe(V-1; V-2); e(V-2; V-1)g > (d 1 - 2(2d 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.
Keyword:
Reprint 's Address:
Version:
Source :
SCIENCE CHINA-MATHEMATICS
ISSN: 1674-7283
CN: 11-5837/O1
Year: 2020
Issue: 2
Volume: 63
Page: 297-308
1 . 3 3 1
JCR@2020
1 . 4 0 0
JCR@2023
ESI Discipline: MATHEMATICS;
ESI HC Threshold:50
JCR Journal Grade:2
CAS Journal Grade:2
Affiliated Colleges: