Bipartition with degree constraint
Bipartition with degree constraint
A well-known result of Stiebitz states that given a graph G and two functions a, b: V(G)-> N such that d_G(v)> a(v)+b(v) for each v, there is a nontrivial vertex partition (A, B), such that d_A(v) >= a(v) for all v in A and d_B(v) >= b(v) for all v in B. In this talk, we will report some results on two analogous open problems. Norin conjectured that if G is a graph with e(G) >= (s+t+1)v(G) for non-negative real number s and t, then there exist a nontrivial vertex partition (A,B), such that e(G[A]) >= s|A| and e(G[B]) >= t|B|. With Csoka, Lo, Norin and Yepremyan, we prove this when s=t. In general, if e(G) >= (s+t+1)(v(G)-1), then there is a vertex partition (A,B), such that e(G[A]) >= s(|A|-1) and e(G[B]) >= t(|B|-1). By using this, we answer a question asked by Reed and Scott. A ``bisection'' is a vertex partition (A,B) with ||A|-|B||\le 1. Bollobas and Scott proposed a conjecture that there exists a bisection (A,B) such that |N_B(v)|>= (d_G(v)-1)/2 for every v in A and |N_A(v)|>= (d_G(v)-1)/2 for every v in B. Recently, with Jie Ma, we proved an approximate result of this conjecture, that |N_B(v)| >= (1/4-f(d_G(v),n))d_G(v) for every v in A and |N_A(v)| >= (1/4-f(d_G(v),n))d_G(v) for every v in B, where f(k,n)->0 when k->0 and n goes to infinity. We also strengthen a result of Kuhn and Osthus.