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

报告题目：Graph Partition with Average Degree Constraint

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

报告地点：1218

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