Lower Bounds for Maximum Weight Bisections of Graphs with Bounded Degrees.

Add to your list(s) Download to your calendar using vCal

• Stefanie Gerke (Royal Holloway)
• Thursday 06 June 2024, 14:30-15:30
• MR12.

If you have a question about this talk, please contact ibl10.

A bisection in a graph is a cut in which the number of vertices in the two parts differ by at most 1. In this talk, we discuss 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, and graphs of (chromatic index) Class 1. 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 Yeo and Yacong Zhou.

This talk is part of the Combinatorics Seminar series.

This talk is included in these lists:

• All CMS events
• All Talks (aka the CURE list)
• CMS Events
• Combinatorics Seminar
• DPMMS Lists
• DPMMS Pure Maths Seminar
• DPMMS info aggregator
• DPMMS lists
• Hanchen DaDaDash
• Interested Talks
• MR12
• School of Physical Sciences
• bld31

Note that ex-directory lists are not shown.