Home >> Seminar 

Graph Partition with Average Degree Constraint
吴河辉 副研究员(国家青年千人，上海数学中心)
Monday, January 1st, 2018, 9:30 AM 华东师范大学 

运筹与控制组学术报告
摘 要：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 $G_1$ and $G_2$ such that $G_1$ has minimum degree at least $s$ and $G_2$ 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 nonnull graph with $e(G)\geq (s+t+1)v(G)$, then there exist a vertex partition $(A,B)$ such that $A \geq s A$, $B \geq 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.



