| Graph theory is a branch of mathematics which is widely used,and its re-search object is graph.The research on graph theory has been over two hundreds years,and it has been greatly developed in many directions.The problem of partition of the vertex set of a graph is an important problem in structural graph theory.The study of partition of the vertex set of a graph has been widely used in many areas of science and engineering,such as computer science,biological science,VLSI physical design and image segmentation.The aim of this thesis is to discuss the partition of graphs.In this thesis,we mainly discuss judicious k-partitions of graphs,maximum balanced 3-partitions and the partition of hypergraphs with edges of size at most two.We construct our work in four chapters.In Chapter 1,we first introduce some basic definitions and notations.Then we describe some definitions and the development of some topics on partition of graphs that we study here.In Chapter 2,we mainly discuss judicious k-partitions of graphs.Let G be a graph with m edges and the maximum cut of k-partitions is(k-1)m/k + α,k ≥2.Then if α≤m/k6,there is a k-partitions V1,..,Vk such that if α>m/k6 and m is sufficiently large(in terms of k),there is a k-partitions V1,...,Vk such that which improves the result of Bollobas and Scott.In Chapter 3,we discuss maximum balanced 3-partitions of graphs.Let G be a graph without isolated vertices and the number of T components which are vertex-disjoint in G is τ.Let △ be the maximum degree of G,then there is a balanced 3-partitions V1,V2,V3 such that e(V1,V2,V3)≥2m/3+n+6τ-△+2/9 K3 is one of its extremal graphs.It extends the result about bisections of graphs which was proposed by Lee,Loh and Sudakov.In Chapter 4,we discuss the partition of hypergraphs with edges of size at most 2.Let G be a hypergraph with mj edges of size j,j = 1,2,then there is a k-partitions V1,...,Vk such that which improves the result of Ma et al.as its last term is O(m24/5). |
