On The Graph Thinkness Problem Of Gross And Harary

The thickness t(G)of a graph G is the minimum number of planar spanning subgraphs into which G can be decomposed.Determining the thickness of a graph is NP-hard problem,thus it is very difficult to obtain the exact number of thickness for arbitrary graphs.Compared with other classical topological invariant,the results about thickness are few.For the thickness of complete bipartite graph Km,n,Beineke,Harary and Moon obtained the following formula in 1964,except the case when m and n are both odd and there exists an integer k satisfying (?).According to the above formula,the thickness of the complete bipartite graph is not completely determined.In 1980,two famous graph theorist Gross and Harary posed the following problem in the paper《Some problems in topological graph theory》:Find the thickness of Km,n for all m,n?In this thesis,we try to study the problem,and we also discuss the thickness of some complete tripartite graphs.Chapter one introduces the thickness of the graph,the background as well as some basic concepts needed in the thesis.At the same time,it also introduces the organization in the thesis.Chapter two introduces the proof for the Beineke-Harary-Moon Thoerem on the thickness of the complete bipartite graph.Chapter three gives the decompositions of the complete bipartite graph Kn,n+4 and Kn,n+8,and determine their thickness.Chapter four studies the thickness of the complete tripartite graph,and determine the thickness for some complete tripartite graphs.