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 m edges, one expects m / 4 edges spans in one vertex class. Bollobas and Scott asked for conditions that guarantee a bisection in which both classes span at most ( 1 / 4 + o ( 1 ) ) m edges simultaneously. Let delta , l be integers with l >= delta >= 2, and let G be a graph with minimum degree delta and m edges. In this article, we prove that if G contains neither triangle nor K delta , l as a subgraph, then G admits a bisection in which both classes span at most ( 1 / 4 + o ( 1 ) ) m edges. We also consider Max-Bisections of graphs without K delta , l and improve a recent result of Hou and Yan.
Keyword:
Reprint 's Address:
Email:
Version:
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 Discipline: MATHEMATICS;
ESI HC Threshold:36
JCR Journal Grade:3
CAS Journal Grade:3
Cited Count:
WoS CC Cited Count: 6
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: