吴文俊数学重点实验室组合图论系列讲座之七十五【颜娟】

题 目 ：Some conjectures about bisection of graphs

报告人：颜娟 博士， 新疆大学

报告时间：2016年1月22号下午 4:30-5:30

地点：1418

摘要：

A bisection of a graph is a balanced bipartite spanning subgraph. Bollobas and Scott conjectured that every 

graph G has a bisectionsuch that for each  . In this talk we will see that for certain complete 

multipartite graphs the conjectured bound is not true. However,  in all those graphs the actual bound 

on the size of a bisection is for each .  Hartke and Seacrest conjectured that every graphic sequence has

 a realization for which the Bollobas-Scott conjecture holds. We will discuss these two conjectures.