Upper bounds on minimum balanced bipartitions

AbstractA balanced bipartition of a graph G is a partition of V(G) into two subsets V1 and V2, which differ in size by at most 1. The minimum balanced bipartition problem asks for a balanced bipartition V1,V2 of a graph minimizing e(V1,V2), where e(V1,V2) is the number of edges joining V1 and V2. We present a tight upper bound on the minimum of e(V1,V2), giving one answer to a question of Bollobás and Scott. We prove that every connected triangle-free plane graph G of order at least 3 has a balanced bipartition V1,V2 with e(V1,V2)≤|V(G)|−2, and we show that K1,3, K3,3−e, and K2,n, with n≥1, are precisely the extremal graphs. We also show that every plane graph G without separating triangles has a balanced bipartition V1,V2 such that e(V1,V2)≤|V(G)|+1