On The Relationship Between The Thickness Of Complete Bipartite Graphs And Complete Tripartite Graphs

A graph G is a triple,consisting of a vertex set V(G),an edge set E(G)and a relation,which makes each edge associated with two vertices(not necessarily different vertices),and these two vertices are called the endpoints of the edge.If a graph can be drawn on the plane so that any two edges do not intersect except at the endpoints,then the graph is a planar graph.The planar graph is one of the key research objects in graph theory.For a non-planar graph,how far it is from a planar graph is also a problem of great concern to graph theorists.Many planarity indexes have been proposed to measure it,such as crossing number,genus,thickness and so on.The research object of this paper is the thickness of the graph.The thickness ?(G)of a graph G is the minimum number of planar subgraphs that decompose a graph G into the union of ?(G)planar subgraphs.It also has important applications in the layout design of large-scale integrated circuits.At present,people have obtained the exact values of the thickness of several graph classes,but there are few studies on the relationship between the thickness of different graph classes.There-fore,this paper mainly starts with the thickness relationship between graph classes,studies the relationship between the thickness of some complete bipartite graphs and complete tripartite graphs,and then obtains the exact values of the thickness of some complete tripartite graphs.In the first chapter,we give a series of related concepts about the thickness of graph,the research background,and introduce the content of each chapter of this thesis briefly.In the second chapter,by using the plane decomposition of complete tripartite graph K1,4p+2,4p+2,the plane decomposition of complete tripartite graph K1,4p+1,4p+3 is constructed,and the thickness relation between complete tripartite graph K1,n,n+1 and complete bipartite graph Kn+1,n+1 is obtained.The thickness relation between com-plete tripartite graph K1,n,n+2 and complete bipartite graph Kn+1,n+2 is obtained,and then we obtain the exact values of the thickness of complete tripartite graph K1,n,n+1 and complete tripartite graph K1,n,n+2.In the third chapter,by using the plane decomposition of complete tripartite graph K2,4p+1,4p+1,the plane decomposition of complete tripartite graph K2,4p,4p+2 is con-structed,and the thickness relation between complete tripartite graph K2,n,n+2 and complete bipartite graph Kn+2,n+2 is obtained,and then we obtain the exact value of the thickness of complete tripartite graph K2,n,n+2.In the fourth chapter,by constructing a plane decomposition of complete tripar-tite graph K1,3p+1,6p+2 and Euler formula,the thickness of complete tripartite graph K1,n,2n is obtained and then the thickness relationship between complete bipartite graph Kn+1,2n and complete tripartite graph K1,n,2n is derived.In the fifth chapter,we sum-marize the full text and give some topics that can be studied in the future.