李海燕, 许宝刚
设V1,V2是图 G 的一个二部划分. 如果 -1≤|V1|-|V2|≤1, 则称V1,V2是 是 G 的 一个二部平衡划分.对于 n 个顶点 n 条边的简单图G, 本文证明了: (1)若 G 是k-正则图(k≥3), 则 G 存在一个最小二部平衡划分 V1,V2,使得 max{e(V1), e(V2}≥(k-1)m/4k; (2) 如果r是大于 4 的实数, 且 当 n 是偶数时Δ(G)≤[(3r-4)/(r+4)]δ(G)-[2r/(r+4)], 当 n是奇数时Δ(G)≤[(3r-4)/(r+4)]δ(G)-[8r/(r+4)],那么 G 存在一个二部平衡划分,使得 min{e(V1), e(V2}≥m/r, 这里 e(Vi) 表示 G 中两个顶点都在 Vi中的边的数目.