On The Graph Thickness Problem Of The Lexicographic Product Of Two Graphs

In graph theory,the lexicographic product or graph composition G · H of graphs G and H is a graph such that:The vertex set of G · H is the Cartesian product V(G)x V(H);and any two vertices(u,v)and(x,y)are adjacent inG · H if and only if either u is adjacent with x in G or u = x and v is adjacent with y in H.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,thus it is very difficult to obtain the exact value of thickness for arbitrary graphs.In this thesis,we will study the thickness of the lexicographic product of two paths,a path and a complete graph.In Chapter 1,we introduce the graph thickness problem and some basic con-cepts of graphs needed in our thesis.In Chapter 2,we study the planarity by introducing the planar graphs and its criterion related in some well known results.In Chapter 3,we introduce two particular classes of graphs:the paths and the complete graphs on which our graph operations will be applied.In Chapter 4,we introduce the basic structures of the lexicographic product showing some of its particularities from others graphs products.In Chapter 5,we study the thickness of lexicographic product for two paths,for a path and a complete graph.