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 cd such 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 thatmin{e(V1,V2),e(V2,V1)}⩾(d−12(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. © 2019, Science China Press and Springer-Verlag GmbH Germany, part of Springer Nature.
Keyword:
Reprint 's Address:
Email:
Source :
Science China Mathematics
ISSN: 1674-7283
Year: 2020
Issue: 2
Volume: 63
Page: 297-308
1 . 3 3 1
JCR@2020
1 . 4 0 0
JCR@2023
ESI HC Threshold:50
JCR Journal Grade:2
CAS Journal Grade:2
Cited Count:
SCOPUS Cited Count: 6
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 1
Affiliated Colleges: