On minimum balanced bipartitions of triangle-free graphs

A balanced bipartition of a graph G is a partition of V(G) into two subsets V (1) and V (2) that differ in cardinality by at most 1. A minimum balanced bipartition of G is a balanced bipartition V (1), V (2) of G minimizing e(V (1),V (2)), where e(V (1),V (2)) is the number of edges joining V (1) and V (2) and is usually referred to as the size of the bipartition. In this paper, we show that every 2-connected graph G admits a balanced bipartition V (1),V (2) such that the subgraphs of G induced by V (1) and by V (2) are both connected. This yields a good upper bound to the size of minimum balanced bipartition of sparse graphs. We also present two upper bounds to the size of minimum balanced bipartitions of triangle-free graphs which sharpen the corresponding bounds of Fan et al. (Discrete Math. 312:1077-1083, 2012).