Neighbour Set(Sum)Distinguishing Total Coloring Of Graphs Embedded In Surfaces Of Nonnegative Euler Characteristic And Tur(?)n Number Of Expansions

Graph theory and Combinatorics is a branch of mathematics.The his-tory dates back to 18th century when Euler published the paper named "The seven bridges of Konigsberg" and now it still has great vitality.It has many applications to computer science,life science and other sciences.At the beginning of this thesis,we work on graph coloring problems.We should claim that the graphs we consider are simple and finite.A(proper)total-k-coloring of a graph G is a mapping ?:V(G)UE(G)?{1,2,...,k} such that any two adjacent elements and incident elements in V(G)U E(G)receive different colors.Let C(v)denote the set of the color of a vertex v and the colors of all incident edges of v.The adjacent vertex distinguishing total-k-coloring of G,or neighbour set distinguishing total-k-coloring of G,is a total-k-coloring of G such that for each edge uv ?E(G),C(u)? C(v).We denote the smallest value k in such a coloring of G by?a"(G).Zhang et al.conjectured that for any graph G with at least two vertices,?A"(G)??(G)+3.It is known that the conjecture is true for any planar graph G with ?(G)>11.In Chapter 2,we improve the result and show that the conjecture holds for graph G which can be embedded in a surface of nonnegative Euler characteristic with ?(G)>10,or ?(G)?8 and G contains no 5-cycle with 2 chords.In Chapter 3,we consider the list version of the adjacent vertex distin-guishing total coloring.For a given graph G =(V,E),let Lx((x?V?E)be a set of lists of real numbers,each of size k.The adjacent vertex distinguishing total choosability of G is the smallest k for which for any specified collection of such lists,there exists an adjacent vertex distinguish total coloring using colors from Lx for each x? V? E,and we denote it by cha"(G).we prove that if G is a planar graph with ?(G)?10,or G is embedded in a surface ?of Euler characteristic ?(?)?0 and ?(G)?>11,then cha"(G)<?(G)+ 3.Given a total-k-coloring of G,let m(v)denote the total sum of colors of the edges incident with v and the color of v.If for each edge uv,m(u)m(v),we call such total-k-coloring a neighbour sum distinguishing total-k-coloring.The smallest number k is called the neighbour sum distinguishing total chromatic number,denoted by ?nsd"(G).It was conjectured that for any graph G with at least two vertices,?nsd(G)+ 3.In Chapter 4.we prove that if G is a planar graph with maximum degree ?(G)? 14,then?nsd(G)??(G)+ 2.Given a graph G,the r-expansion G(r)is the r-graph obtained by en-larging each edge of G into an r-set by using new vertices such that different edges are enlarged using disjoint sets of expansion vertices.Let exr(n,H)be the maximum number of edges in an r-graph with n vertices not containing a given r-graph H,which is called the Tur(?)n number of H.A set of vertices in a hypergraph H containing exactly one vertex from every edge of H is called a crosscut.If it exists,then we use ?(H)to denote the minimum size of a crosscut of H.In Chapter 5,we prove that for sufficiently large n,exr(n,G(r))?(?,(G)-1 +o(1))(r-1n),when r?5 and the treewidth of graph G is at most 2.