侯建锋: On bisections of H-free graphs

：侯建锋 教授

A bisection of a graph $G$ is a partition of its vertex set into two sets which differ in size by at most 1, and its size is the number of edges between the two sets. The Max-Bisection problem is to find a bisection of $G$ maximizing its size. There are little results on Max-Bisections of graphs. The talk concerns Max-Bisections of $H$-free graph for some special graph $H$. Bollob\'as and Scott [Problems and results on judicious partitions, Random Struct. Alg. 21 (2002) 414--430] asked for conditions that guarantee a bisection of a graph with $m$ edges in which each class has at most $(1/4+o(1)\big)m$ edges. We demonstrate that cycles of length 4 play an important role for this question, and give some results on this topic.