On Min‐Bisections of Graphs

ABSTRACT A bisection of a graph is a bipartition of its vertex set in which the number of vertices in the two parts differ by at most 1, and its size is the number of edges which go across the two parts. Let be a graph with vertices and edges. Bollobás and Scott asked the following: What are the largest and smallest cuts that we can guarantee with bisections of ? There are reasonable sufficient conditions such that has bisections of size at least for some . In this paper, we study the Min‐Bisection problem which has arisen in numerous contexts, and initially give some sufficient conditions such that has bisections of size at most for some .