On Judicious Bisections of Graphs

Title: On Judicious Bisections of Graphs


Speaker: Prof. Xingxing Yu (Georgia Institute of Technology)


Time: 4:00-5:00 pm; June 6; 2013


Place: Conference Room A304, Department of Mathematical Sciences


AbstractA bisection of a graph G is a bipartition $S_1,S_2$ of V(G) such that $||S_1|-|S_2||\le 1$. It is NP-hard to find a bisection $S_1,S_2$ maximizing $e(S_1,S_2)$ (repectively, minimizing $\max\{e(S_1),e(S_2)\}$), where $e(S_1,S_2)$ denotes the number of edges from $S_1$ to $S_2$, and $e(S_i)$ denotes the number of edges of $G$ with both ends in $S_i$. There has been extensive research on bisections from algorithmic point of view, but very few extremal results are known. Bollob\'{a}s and Scott conjectured that if $G$ is a graph with $m$ edges and minimum degree at least $2$ then $G$ admits a bisection $S_1,S_2$ such that $e(S_i)\le m/3$ for $i=1,2$. In this paper, we confirm this conjecture and show that any extremal graph is a disjoint union of triangles. Joint work with Baogang Xu.


ContactMei Lu