运筹与控制组学术报告

摘 要：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 non-null 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.