图的平衡公平划分

The graph partition problems refer to partitioning vertex set into several disjoint subsets. Such that the subsets have some expected properties.The graph partition problems are widely used in the computer field, and has been one of the hot problems in graph theory.It contains many important problems in graph theory. For example classic coloring problem and the famous Max cut problem. A balanced partition is to partition the vertex set into subsets which contain equal vertice as possible.Bollobas and Scott conjecture that every graph G with minimum degree at least 2 admits a balanced bipartition such that every subset contains less than or equal to m/3 edges, where m is the number of edge in G. We has proved this conjecture for all graphs with average degree greater than or equal to 6.This project mainly studies on the balanced partition problem .And hope this conjecture has further breakthrough. We also study on the max cut problem of balanced partition.

图的划分问题是指把图的顶点集划分成一些互不相交的子集的并, 使得划分之后的子集或子集之间满足某些条件. 图的划分问题早期就在计算机领域有着广泛应用，并且一直是图论研究的热点问题之一. 它包含了许多图论中的重要问题．例如经典的着色问题和著名的最大割问题。如果划分中的每个子集所包含的顶点数目尽量平均，也就是说任意两个子集所包含的顶点数目相差不超过1，则称它是一个平衡划分. Bollobas 和Scott 提出了下述猜想:设G 是一个最小度至少为2 的图, 则G 存在顶点集V (G)的平衡二部划分，使得每个子集的导出子图所包含的边数都不超过G的边数的三分之一。已经证明了这个猜想对所有平均度大于或等于6 的图都成立.本项目主要研究图的平衡划分问题，力求在这一猜想上有更进一步的突破。并研究与平衡公平划分有关的最大割问题

图的顶点划分问题包含了很多图论研究中的核心问题。例如各种各样的着色问题和备受关注的最大割问题。这些问题在现实中也有着广泛的应用。Bollobas 和 Scott 在1993年提出了图的公平划分问题(judicious partition problem): 给定一个图 G，找它的顶点集的一个划分使得顶点集的某些子集同时满足某个限制条件。公平划分问题的一个例子是由Entriger提出的瓶颈二部划分问题。2002年，Bollobas 和 Scott 又提出了平衡公平划分问题，此问题要求对图的顶点集的划分是尽量平均的。同时，他们提出猜想：设G是一个最小度至少为2的图, 则G 存在顶点集的平衡二部划分使得每一部分导出子图所包含的边数不超过m/3。2010年，我们证明了这个猜想对于最小度大于等于6的图都成立。在本项目中，我们对这个猜想进行了进一步的研究。我们还研究了平衡最大割与平衡划分之间的关系，给出了一些平衡最大割下界的极图以及一些特殊图类平衡最大割与平衡划分的确切值。另外，我们还对图的谱以及特殊图类的特征多项式做了一些研究。