The 2-distance Vertex-distinguishing Total Coloring Of Graphs

A proper total coloring of a graph G is a mapping<?:V(G)? E(G)? {1,2,...,k}such that ?(x)? ?(y)for any two adjacent or incident elements x.y ? V(G)U E(G).The total chromatic number X"(G)of a graph G is the smallest integer k such that G has a total coloring using k colors.For a total k-coloring ? of G,we use C?(v)={?(v)} ? {?(xv)|xv ? E(G)} to denote the set of colors assigned to a vertex v and those edges incident to v.An adjacent vertex-distinguishing total coloring of a graph G is a proper total coloring 0 such that any adjacent vertices have distinct sets of colors.The adjacent vertex-distinguishing total chromatic X"a(G)of a graph G is the smallest integer k such that G has an adjacent vertex-distinguishing total coloring using k colors.A 2-distance vertex-distinguishing total coloring of a graph G is a proper total coloring of G such that any pair of vertices at distance 2 have distinct sets of colors.The 2-distance vertex-distinguishing total chromatic number Xd2"(G)is the smallest integer k such that G has a 2-distance vertex-distinguishing total coloring using k colors.Behzad and Ving posed independently the following famous conjecture:For any graph G,X"(G)?(G)+ 2.In 2005,Zhang et al.introduced the adjacent vertex-distinguishing total coloring and gave the following conjecture:Every graph G with at least two vertices has Xa"(G)??(G)+ 3.Huang et al.proved that every graph G with?(C)>3 satisfies xa"(G)? 2?(G).Later,Coker and Johannson showed that every graph G satisfies xa"(G)? ?(G)+ c,where c is a constant.In this master thesis,we study 2-distance vertex-distinguishing total coloring of graphs.In Chapter 1,we collect some basic notations,give a chief survey in this direction and state the main results obtained.In Chapter 2,we study the 2-distance vertex-distinguishing total coloring of some special graphs such as paths,trees,cycles,unicycle graphs,and three types of Cartesian products.The main results are as follows:(1)Characterize the 2-distance vertex-distinguishing total chromatic of unicycle graphs.(2)Determine the 2-distance vertex-distinguishing total clhromatic of three types of Cartesian products.In Chapter 3,we show that the 2-distance vertex-distinguishing total chromatic of a Halin graph is at most ?(G)+ 3.In Chapter 4,we show that the 2-distance vertex-distinguishing total chromatic of an outerplanar graph is at most ?(G)+ 3.