Embeddability Of Graphs And Coloring Of Set System

In this thesis , we study graph embeddings and colorings of set system .In the first part of this paper , we investigate the fundamental cycles in a graph G and their applications in graph embeddings . We show that a graph G may be embedded in an orientable surface with genus at least g if and only if for any spanning tree T , there exists a sequence of fundamental cycles C₁,C₂,…,C_2g with C_2i-1∩C_2i≠φfor 1≤i≤g.As a consequence , any two spanning trees T₁ and T₂ of G have the same number of maximum number of such adjacent fundamental cycle pairs.(In fact,this number is _γM(G),the maximum genus of G).This implies that we may construct an orientable embedding with large genus of a graph G from any spanning tree T which may have very large number of odd components in G\E(T). This is quite different from the earlier work of X uong^[5] where spanning trees with small odd components are needed . As applications,we may use this result to locate the maximum genus of a graph with an edge-cut.Some known results are also concluded .In the second part of this paper , we consider a special graph G_Cn^r which is determined by subsets of a given set,where V(G) = {u | u =A_i,A_i={x₁,x₂,…x_r} (?) A = {1,2,…n}} and E(G) = {e | e = uv , u ,vεV(G) ,|u (?) v| =2}. We proof the following results:â‘ There exists Hamilton cycle in every graph G_Cn^r.â‘¡Every graph G_Cn^r is up-embeddable .â‘¢X(G) = n,when n is odd;X(G) = n - 1,when n is even.