Maximum bisections of graphs without short even cycles

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. In this paper, motivated by several known results of Alon, Bollobas, Krivelevich and Sudakov about Max-Cut, we study maximum bisections of graphs without short even cycles. Let G be a graph on medges without cycles of length 4 and 6. We first extend a well-known result of Shearer on maximum cuts to bisections and show that if G has a perfect matching and degree sequence d(1), ..., d(n), then G admits a bisection of size at least m/2 + Omega (Sigma(n)(i=1) root d(i)). This is tight for certain polarity graphs. Together with a technique of Nikiforov, we prove that if G also contains no cycle of length 2k >= 6 then G either has a large bisection or is nearly bipartite. As a corollary, if G has a matching of size circle minus(n), then G admits a bisection of size at least m/2 + Omega (m((2k+1)/(2k+2)) and that this is tight for 2k is an element of {6, 10}; if G has a matching of size o(n), then the bound remains valid for Gwith minimum degree at least 2. (C) 2021 Elsevier Inc. All rights reserved.