Description
A cut is a partition of the vertices of a graph into two disjoint subsets. A bisection in a graph is a cut in which the number of vertices in the two parts differs by at most 1. The MAX-BISECTION (MAX-CUT) problem is to find a bisection (cut) that maximizes the number of edges in the bisection. Both of these two problems are known to be NP-hard. Thus, many researchers worked on finding some good lower bounds for the maximum bisection (or cut) in graphs. In this talk, I will introduce some new lower bounds for the maximum weight of bisections of edge-weighted graphs with a bounded maximum degree, which improve a bound proved by Lee, Loh, and Sudakov for (unweighted) maximum bisections in graphs whose maximum degree is either even or equals 3, and for almost all graphs. I will show that a tight lower bound for the maximum size of bisections in 3-regular graphs obtained by Bollobás and Scott can be extended to weighted subcubic graphs. I will also talk about edge-weighted triangle-free subcubic graphs and show that a much better lower bound (than for edge-weighted subcubic graphs) holds for such graphs with only one exceptional graph. This talk is based on a joint work with Stefanie Gerke, Gregory Gutin, and Anders Yeo.| Period | 20 Mar 2024 |
|---|---|
| Held at | Department of Mathematics |
| Degree of Recognition | Local |