Lower Bounds for Maximum Weight Bisections of Graphs with Bounded Degrees

Stefanie Gerke ( Royal Holloway University of London )

A bisection of a graph is a cut in which the number of vertices in the two parts of the cut differ by at most 1. In this talk, we give lower bounds for the maximum weight of bisections of edge-weighted graphs with bounded maximum degree. Our results improve a bound of Lee, Loh, and Sudakov (J. Comb. Th. Ser. B 103 (2013)) for (unweighted) maximum bisections in graphs the maximum degree of which is either even or equals 3. We show that a tight lower bound for maximum size of bisections in 3-regular graphs obtained by Bollob\'as and Scott (J. Graph Th. 46 (2004)) can be extended to weighted subcubic graphs. This is joint work with Gregory Gutin, Anders Yao and Yacong Zhou.