## On judicious bisection of graphs

- May 17, 2013
- 11 a.m.
- LeConte 312

## Abstract

Bollobas and Scott conjectured that every graph with $m$ edges and minimum degree at least 2 has a bisection $V _ 1, V _ 2$ of which each spans at most $m/3$ edges. We confirm this conjecture, and characterize the extremal graphs. This is a joint work with Dr. X. Yu.