On The Adjacent Vertex Distinguishing Total Coloring Of Some Graphs

The coloring problems is one of popular problems in graph theory because of it's profound significance in both theory and practice. Until now, there have been rather abundant results. In 2004, Zhang Zhongfu introduced the conception of adjacent vertex distinguishing total coloirng for graph in the litereture[12]:Let G be a connected simple graph on n ≥2 vertices, A;be a positive integer and f be a mappling from V(G) U E(G) to {1,2,…, k}. Let C(u) = {f(u)} ∪ {f(uv) | uv ∈ E(G),v ∈ V(G)} for every v ∈ V(G). If(1) for every uv, vw G E(G), u ≠ w, we have f(uv) ≠ f(vw);(2) for every uv ∈ E(G), we have f(u) ≠ f(v), f(u) ≠ f(uv), f(v) ≠ f(uv), then f is called a k-proper total coloring of graph G. Forthermore, if f satisfies(3) for every uv G ∈(G), we have C(u) ≠ C(v),then f is called a k-adjacent vertex distinguishing total coloring of G (k-AVDTC for short). The number min{k| G has a k—adjacent vertex distinguishing total coloring} is called the adjacent vertex distinguishing total chromatic number and denoted by X_at(G), where C(u) is the set of the colors of u and edges which is adjacent to u.After this conception be proposed, only a few works have been done, because it's complex. So far, just have the adjacent vertex distinguishing total chromatic number of graphs such as path, cycle, tree, complete graphs, etc. In this paper, we main investigated the problem of the adjacent vertex distinguishing total coloring of some special graphs. In chapter 2, using the analysis structure and the mothod of adding auxiliary edges in a graph, we obtained the adjacent vertex distinguishing total chromatic number of the 1-cycle. In chapter 3, by using induction method, we obtained the adjacent vertex distinguishing total chromatic number of 2-connected outerplane graph with Δ(G) ≤ 3. In chapter 4, based on θ-graph, also by using induction method, we obtained the adjacent vertex distinguishing total chromatic number of extended θ-graph. We give the main results as following:Theorem Let G be a 1-cycle, then the following holds: (a) If G be a cycle, then(b) If G be a 1-cycle but not cycle, then= f A(G) + 1, E(G[VA}) = 0;Xat[ \ A(G) + 2, E(G[yA]) ^ 0.Theorem Let G be a 2-connected outerplane graph with A(G) < 3, then Xat(G) = 5.( k+2, uv e E{6k).