Decomposition of graphs under average degree condition
- Series
- Graph Theory Seminar
- Time
- Thursday, September 29, 2016 - 13:30 for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Yan Wang – Math, GT
Stiebitz showed 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 conjectured that a graph with average degree s+t+2 can be decomposed
into vertex disjoint subgraphs G_1 and G_2 such that G_1 has average degree
at least s and G_2 has average degree at least t. Recently, we prove
that a graph
with average degree s+t+2 contains vertex disjoint subgraphs G_1 and G_2
such that G_1 has average degree at least s and G_2 has average degree at
least t. In this talk, I will discuss the proof technique. This is joint
work with Hehui Wu.