Research On The Properties Of Graphs Embedded On Surface

In this dissertation,we study some important properties of graphs embedded on surface.This dissertation contains the following five chapters.In Chapter 1,we introduce the background and some relevant basic concepts of this dissertation.In Chapter 2,we investigate the coloring extension of planar graphs.Let G be a planar graph and W = W1?W2 ?…? Wm be a subgraph of G,where each Wi is a complete subgraph with |V(Wi)| ? k.Suppose that any two components of W are at distance at least d.It is known that any proper 5-coloring of W can be extended to a proper 5-coloring of G provided d ? 6k-2.Albertson and Moore[3]improved the distance constraint to 4k for such coloring extension.Up to now,it is the best possible with respect to distance constraint.Indeed,Albertson and Moore[3]proved that there exists a graph G such that some proper 5-coloring of W can not be extended to a proper 5-coloring of G when d = 4k-2.However,whether such coloring extension can be finished when d = 4k-1 is still unknown.In this chapter,we focus on a special case that each Wi is a K2 and obtain sufficient conditions for such coloring extension when d>4,d>6 and d>7.Our results show that the structures that hinder the coloring extension when d>4,d>6 and d?7 are 3-cycles and 4-cycles of G.In Chapter 3,we study the coloring problem of graphs embedded on surface.According to Thomassen's theory,coloring extension of planar graphs is an impor-tant technique of solving coloring problems of graphs embedded on surface.Specifi-cally,if G has a triangulation on a surface with large edge-width,then G contains a collection of chordless disjoint cycles {C1,C2,…,Ct} such that cutting the surface along these cycles will yield a planar graph G'.It provides an original idea for our s-tudy.Obviously,after the cutting process,each Ci produces a pair of cycles {C'i,C"i}which corresponds to two non-triangle face boundaries of G'.If we obtain a proper 5-coloring,say f,of G' satisfying f(C'i)?f(C"i)for 1 ? i ? t,then identifying such cycle pairs yields a proper 5-coloring of G.Therefore,in this chapter,we will first finish the coloring extension from a initial coloring of some disjoint cycles,and then give a 5-color theorem for graphs embedded on surface.Obviously,our result,together with Thomassen's theory(Theorem 3.3 in[43]),will form a more effective way to solve the coloring problem of graphs embedded on surfaces.It is known that each strong embedding scheme II of G on a surface determines a signature an:E(G)? {±1}.We say that the signed graph(G,??)is induced by the embedding II.In 1983,Bouchet[9]conjectured that every flow-admissible signed graph admits a nowhere-zero 6-flow.DeVos[14]proved that such signed graphs admit nowhere-zero 12-flow.It is the best approach to the conjecture until now.In Chapter 4,we just consider the signed graph(G,??)induced by embedding scheme ?,and prove that if G has a strong embedding on a non-orientable surface S and it is k-face-colorable on S,then the signed graph(G,??)admits a nowhere-zero k-flow.It displays a connection between integer flow of signed graphs and face coloring.Then we prove that some special signed graphs(G,an)admit nowhere-zero 8-flow.In Chapter 5,we investigate the minimum genus problem of the 3-regular apex graphs.By using the technique of switching bridges,we prove our main theorem.Let G be a 3-regular apex graph with apex x,and N(x)= {?,?,?} be the neighbor of x.Denote by G-x the new graph obtained by suppressing the vertices with degree 2 in G-x.Suppose that G-x is 3-connected,and ? is a plane embedding of G-x.Mohar[32]proved that if any two vertices in N(x)are at face distance at least 4 in ?,then g(G)= 2.Based on this theory,we further prove that if any two vertices in N(x)are at face distance at least 2 and the summation of face distance between any two vertices in N(x)is greater than 7 in ? then g(G)= 2.Obviously,our result is an improvement on Mohar's theorem[32]with respect to the face distance.