Home   Overview   Faculty   Research   Undergraduate Programs   Graduate Programs   Position Available   Contact Us

Previous Next
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 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.
Links >>
Resources >>
  Other Links >>    Shanghai Mathematical Society    Chinese Mathematical Society    American Mathematical Society    The European Mathematical Society  
       Copyright 2012 All rights reserved    Department of Mathematics, East China Normal University    Tel: 86-21-54342609