Bisections of graphs without K2,l

Let G be a connected graph with n vertices, m edges, minimum degree delta >= 2, and maximum degree Delta. Fan et al. (2018) showed that G admits a bisection of size at least m/2 + n-1/4 if it has girth at least 5, and admits a bisection of size at least m/2 + n-1/4 - vertical bar M vertical bar/2 delta f it has no 4-cycles, where M is a maximum matching of G. Let l >= 2 be an integer. In this paper, we present a polynomial time algorithm for finding a bisection of size at least m/2 + n-1/4 in G if G has neither 4-cycles nor triangles at distance 2. We also prove that G admits a bisection of size at least m/2 + n-l+1/4 if it has no K-2,K-1, and with further restriction that either (1) G has no triangles of distance 2 (this improves a result of Fan, Hou, and Yu), or (2) G is an Eulerian graph. For k >= 2, we show that, restricting to n = o(m) or Delta = o(n), G admits a balanced k-partition such that the number of edges in each part is at most m/k(2) + o(m) provided n is sufficiently large. (C) 2018 Elsevier B.V. All rights reserved.