最大度与最小度相差不超过2的图的平衡judicious划分

图G的顶点集V(G)的一个二部划分V_1和V_2叫做平衡二部划分,如果||V_1|-|V_2||≤1成立.Bollobas和Scott猜想:每一个有m条边且最小度不小于2的图,都存在一个平衡二部划分V_1,V_2,使得max{e(V_1),e(V_2)}≤m/3,此处e(V_i)表示两顶点都在V_i(i=1,2)中的边的条数.他们证明了这个猜想对正则图(即△(G)=δ(G))成立.颜娟和许宝刚证明了每个(k,k-1)-双正则图(即△(G)-δ(G)≤1)存在一个平衡二部划分V_1,V_2,使得每一顶点集的导出子图包含大约m/4条边.这里把该结论推广到最大度和最小度相差不超过2的图G.

Balanced judicious partitions of graphs with $\Delta($G$)-\delta($G$)\leq$2

A bipartition $V_{1}$ and $V_{2}$ of $V(G)$ of a graph $G$ is balanced if $||V_{1}|-|V_{2}||\leq1$. Bollob\'{a}s and Scott conjectured that every graph with $m$ edges and minimum degree atleast 2 admits a balanced bipartition $V_{1}$, $V_{2}$ such that {\rm max}$\{e(V_{1}), e(V_{2})\}\leq\frac{m}{3}$, where $e(V_{i})$ denoted the number of edges of $G$ with both ends in $V_{i}(i=1, 2)$. They showed that this conjecture held for regular graphs(i.e., when $\Delta(G)=\delta(G)$). Yan Juan and Xu Baogang showed that every ($k$, $k-1$)-biregular graph(i.e., $\Delta(G)-\delta(G)\leq1$) admitted a balanced bipartition into $V_{1}$, $V_{2}$ with about $\frac{m}{4}$ edges in each vertex class. In this paper we extend this result to graphs with $\Delta($G$)-\delta($G$)\leq2$.