On bisections of graphs without complete bipartite graphs.

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. Bollobás and Scott asked for conditions that guarantee a bisection in which both classes span at most (1∕4+o(1))m edges simultaneously. Let δ,ℓ be integers with ℓ≥δ≥2, and let G be a graph with minimum degree δ and m edges. In this article, we prove that if G contains neither triangle nor Kδ,ℓ 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δ,ℓ and improve a recent result of Hou and Yan. [ABSTRACT FROM AUTHOR]