科研之友
微信
新浪微博
Facebook
分享链接
摘要
A balanced bipartition of a graph G is a bipartition V-1 and V-2 of V (G) such that -1 <= vertical bar V-1 vertical bar - vertical bar V-2 vertical bar <= 1. Bollobas and Scott conjectured that if G is a graph with in edges and minimum degree at least 2 then G admits a balanced bipartition V-1, V-2 such that max{e(V-1), e(V-2)} <= m/3, where e(V-i) denotes the number of edges of G with both ends in V-i. In this note, we prove this conjecture for graphs with average degree at least 6 or with minimum degree at least 5. Moreover, we show that if G is a graph with m edges and n vertices, and if the maximum degree Delta(G) = o(n) or the minimum degree delta(G) -> infinity, then G admits a balanced bipartition V-1, V-2 such that max{e(V-1), e(V-2)} <= (1 + o(1))m/4, answering a question of Bollobas and Scott in the affirmative. We also provide a sharp lower bound on max{e(V-1, V-2) : V-1, V-2 is a balanced bipartition of G}, in terms of size of a maximum matching, where e(V-1, V-2) denotes the number of edges between V-1 and V-2.
