报告人：吴河辉 复旦大学/上海数学中心

报告题目：Graph Partition with Average Degree Constraint

报告时间：周5，下午3-4点

报告地点：1218

摘要： A classical result showed by Stiebitz in 1996 stated that a graph with minimum degree s+t+1 can be decomposed into vertex disjoint subgraphs G1 and G2 such that G1 has minimum degree at least s and G2 has minimum degree at least t. Motivated by this result, Norin raised the conjecture that for any nonnegative real number s and t, such that if G is a non-null graph with e(G) ≥ (s + t + 1)v(G), then there exist a vertex partition (A, B) such that ||A|| ≥ s|A|, ||B|| ≥ t|B|. Recently, we prove the weaker version of the conjecture, that there exists two vertex set A and B that satisfied the required average degree constraint. This is joint work with Yan Wang at Georgia Institute of Technology.