Research On Judicious Partitions Of Graphs

This paper mainly studies the problem of judicious partitions of graphs. Bases on Bollobas and Scott’s problem: Does any graph G of size m have a partition of proposed by them:every graph with m edges and minimum degree at least2admits a balanced bipartition V1V2, such that max{e(v1),e(V2)}≤3m, where e(V1) denotes the number of edges of G with both ends in V,(i=1,2). We study the problem of judicious3-partitions of graphs and balanced judicious partitions of graphs with A(G)-δ(G)≤2. At the same time, we improve the bounds given by YuXingxing, XuBaogang and Yan-Juan. And the new bounds is more closer to the problem and conjecture.In chapter1:we give some definitions and research background about the problem of judicious partitions of graphs in detail and introduce the structure and content of each chapter of this paper.In chapter2:we summarize some recent conclusions about the problem of judi-cious3-partitions of graphs as well as balanced judicious partitions of regular graphs and (k, k-l)-biregular graphs.In chapter3:we mainly study the problem of judicious3-partitions of graphs, which is a case of judicious k-partitions of graphs. When k=3, we improve Yu and Xu’s result about this problem.In chapter4:we give the result of balanced judicious partitions of graphs with A(G)-δ(G)≤2, which covers Yan and Xu’s conclusion about the balanced judicious partitions of (k, k-l)-biregular graphs.In chapter5:we list some open problems about judicious partitions and some considerations about these problems.