Hehui Wu

Vertex Partition with Average Degree Constraint

Date: 5/31/2018
Time: 3:00PM-4:00PM
Place: 315 Armstrong Hall

Abstract: A classical result, due to Stiebitz in 1996, states that a graph with minimum degree $s+t+1$ contains a vertex partition $(A, B)$, such that $G[A]$ has minimum degree at least $s$ and $G[B]$ has minimum degree at least $t$. Motivated by this result, it was conjectured that for any non- negative real number s and t, such that if G is a non-null graph with average degree at least $s + t + 2$, then there exist a vertex partition $(A, B)$ such that $G[A]$ has average degree at least $s$ and $G[B]$ has average degree at least $t$. Earlier, we claimed a weaker result of the conjecture that there exist two disjoint vertex set $A$ and $B$ (for which the union may not be all the vertices) that satisfy the required average degree constraints. Very recently, we fully proved the conjecture. This is joint work with Yan Wang at Facebook.

Hehui Wu

All are welcome.

Date, Location:
2018-05-31