Indexed by:
Abstract:
A bisection of a graph is a bipartition of its vertex set in which the two classes differ in size by at most one. For a random bisection of a graph with (Formula presented.) edges, one expects (Formula presented.) edges spans in one vertex class. Bollobás and Scott asked for conditions that guarantee a bisection in which both classes span at most (Formula presented.) edges simultaneously. Let (Formula presented.) be integers with (Formula presented.), and let (Formula presented.) be a graph with minimum degree (Formula presented.) and (Formula presented.) edges. In this article, we prove that if (Formula presented.) contains neither triangle nor (Formula presented.) as a subgraph, then (Formula presented.) admits a bisection in which both classes span at most (Formula presented.) edges. We also consider Max-Bisections of graphs without (Formula presented.) and improve a recent result of Hou and Yan. © 2021 Wiley Periodicals LLC
Keyword:
Reprint 's Address:
Email:
Source :
Journal of Graph Theory
ISSN: 0364-9024
Year: 2021
Issue: 4
Volume: 98
Page: 630-641
0 . 9 2 1
JCR@2021
0 . 9 0 0
JCR@2023
ESI HC Threshold:36
JCR Journal Grade:3
CAS Journal Grade:3
Cited Count:
SCOPUS Cited Count: 8
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 1
Affiliated Colleges: