Balanced Partitions Of Graphs

Graph partition problem is one of the most important topics in structural graph theory.This paper mainly studies the problem of balanced judicious partition of graphs and maximum balanced4-partitions of a graph.In the first chapter,we introduce the research background and some definitions about the prob-lems of graph partition.In addition,we introduce balanced judicious partition problem and maximum balanced partition problem in detail.In the second chapter,we summarize some recent progresses about the problems of balanced judicious partition of graphs.we give a result of balanced judicious partition of graphs with??G?-??G??t-1,which extends Yan,Xu,Hu and He's results.In the third chapter,we study the problems of maximum balanced 4-partition of graphs and show that for a graph G with m edges if r is a real number and??G??_5r-8^r+24??G?-^18r_5r-8,then G admits a maximum balanced 4-partition V₁,V₂,V₃,V₄ such that max{e?V_i?}?_r^m?i=1,2,3,4?.