Adjacent Vertex-distinguishing Total Colorings Of Graphs

The coloring problem is one of primary fields in the study of graph theories. The coloring problem and someother graph theories are all from the study of the celebrated four color problem. With the application of the coloring problem some scholars presented and studied a few coloring problem with different restriction.A proper k-coloring of graph G is an assignment of k colors to each vertiex in such a way that adjacent vertices have distinct colors.Difine the chromatic number of G asχ(G) = min{k|graph G has k - coloring s}. Similar,a proper k-edge-coloring of graph G is an assignment of k colors to each edge so that no two adjacent edges have the same color.The edge-chromatic number is defined asλ′(G) = min{k|graph G has k - edge - colorings}.The totle coloring is a generalization of the coloring and the edge coloring.It's a traditional coloring problem and was introduced by Vizing(1964) and independently Behzad(1965).the total coloring is defined as all of vertices and edges of the graph are colored in such a way that no two adjacent or incident elements are colored the same.On the basis of the total coloring,Zhang Zhongfu presented the concept of the concept of the adjacent vertex-distinguishing total colorings and gave the conjecture and two results.The definition of adjacent vertex-distinguishing total coloring by Zhang Zhongfu is as follows : Let G(V,E) is a simple and connected graph of which the order is at least 2,k is an positive integer and f is the mapping from V(G)∪E(G) to C = {1,2,…,k}orC[k]. For any vertex u∈V(G) , denote C(u) = {f(u)}∪{f(u,v)|uv∈E(G)} . (?)(u) = C- C(u) .(1) For any edge uv , vw∈E(G) , and u≠w,there is f(uv)≠f(vw) .(2) For any edge uv∈E(G) ,and u≠v,there is f(u)≠f(v),f(u)≠f(uv), f(uv)≠f(v) .(3) For any edge uv∈E(G) , and u≠v, there is C(u)≠C(v) .If (1) , (2) are satisfied , then f is called a k-total coloring of graph G(in brief, it is noted as k-TC) .If (1), (2) , (3) are satisfied , then f is called a k-adjacent vertex-distinguishing total coloring of graph G (in brief. it is noted as k-AVDTC) .The total chromatic number of G isχ_T (G)= min{k|G has k-TC}.The adjacent vertex-distinguishing total chromatic number of G isλ_at(G) = min{k| G has k-AVDTC}.The following results about adjacent vertex-distinguishing total coloring are right . apparently .For a simple connected graph G of order n (n = |V(G)|≥2) , adjacent vertex-distinguishing total chromatic numberχ_at(G) exist , andχ_at(G)≥△(G) + 1.If G(V,E) has two adjacent maximum degree vertices , thenχ_at(G)≥△(G) + 2.The following conjecture is proposed by Zhang Zongfu in :For a simple connected graph G of order n (n = |V(G)|≥2) , thenχ_at(G)≤△(G) + 3. The adjacent vertex-distinguishing total chromatic number of some graphs such as path,circle,complete graph, 2-complete graph . star . fan . wheel and tree have been abtained. We also have obtained the adjacent vertex-distinguishing total chromatic number of the Mycielski graph,link graph the Cartesian product graph,Petersen graph,Heawood graph Tomassen graph,the Haj(o|¨)s sum of W_n,etc. These results are satisfied the conjecture .The problem of determining the adjacent vertex-distingguishing total chromatic number of a graph is NP-hard.In this article we mainly deals with the adjacent vertex-distinguishing total chromatic number for some special graphs and the graphs under some graph's operation.In this artical we get these following conclusions:Graph's Insert operation:There are graphs G.H and |V(G)|=|V(H)|,the insert operation of G to H is using every vetex of G dissect each edge of H and the edges of G immovabily.Vertex expanding graph: As G is a graph we get the v(H) expending graph of G by replacing the vertex v of G a graph H,but each adjacent vertex of v just adjact to one vertex of H, that is the degree of v don't change.Hajós sum:Let G₁ and G₂ be vertex disjoint graphs containing edges x₁y₁∈E(G₁) and x₂y₂∈E(G₂).The Hajós sum : G = (G₁,x₁y₁)+(G₂,x₂y₂) of the pairs (G₁,x₁y₁) and (G₂,x₂y₂) is obtained from G₁∪G₂ by indentifying x₁ and x₂, deleting the edge x₁y₁, x₂y₂, and adding the edge y₁y₂.Vertex dissecting graph: As G is a graph,the vertix dissecting graph of G is obtained from G by replacing each vertex by tow independent vertices,denotedby G[I₂].The first class graph: If G have adjactent verties of most degree andχ_at(G) = â–³(G)+2,then G is a first class graph.The secend class graph: If G have adjactent verties of most degree andχ_at(G) =â–³(G) + 3,then G is a secend class graph.We briefly summerize our main results as following:Theorem 2.1.1 Insert K_n into C_n, V(K_n) = {v₁,…,v_n}, V(C_n) = {u₁,…,u_n}.We get graph S_n (n≥3).It is a graph that V(S_n) = {v₁,…,v_n;u₁,…,u_n}; E(S_n) ={v_iv_j,v_iu_i|i,j = 1,…,n}∪{u_iv_i+1,u_nv₁|i= 1,…,n - 1}; Then we haveχ_at(S_n) =â–³(S_n) + 2.Theorem 2.1.2 Insert W_n into C_n+1,V{W_n) = {v₁,…,v_n,w},V(C_n+1) = {u₁,…,u_n+1}. We get graph G. It is a graph that V(G) = {v₁,…,v_n.w;u₁,…,u_n-1};E(G) = {wv_i,v_iu_i,u_iv_i+1,wu₁,wu_n+1|i = 1,…,n;v_n+1 is v₁};Then we haveλ_at(G) =â–³(G) + 1 = n + 3{n≥4).Theorem 2.1.3 Insert H into C_n, V(H) = {v₁,…,v_n},V(C_n) = {u₁,…,u_n}.We get graph G′.It is a graph that V(G′) = {v₁,…,v_n; u₁,…,u_n}; E(G′) = {v_iu_i,v_iu(i+1), |i = 1,…,n:u_n+1 is u₁}:∪E{H).If H satisfy the conjecture of adjacent vertex-distinguishing total coloring thatχ_at(H)≤△(H) + 3. Then we haveχ_at(G′)≤△(G′) + 3.Theorem 2.2.1 Pⁿ is a graph that V(Pⁿ) = {u,v,w,v₁,…,v_n};E{Pⁿ)={uv_i,vv_i, vw|i = 1,…,n}∪{v_iv_i+1|i = 1,…,n - 1}: Then we haveTheorem 2.2.2 Let G₂ be the u(K_n) expanding graph of Pⁿ,V(Pⁿ) = {u,v, w, v₁,…,v_n}: V(K_n) = {u₁,…,u_n}; and for u_i∈K_n, v_i∈Pⁿ we make u_iv_i∈ G₂ (i = 1,…,n);Then we haveTheorem 2.2.3 Let H₁ be a u(S_n) expanding graph of Pⁿ,V(S_n) = {v₁,…,v_n;u₁,…,u_n}; E(S_n) = {v_iv_j,v_iu_i|i,j = 1,…,n]∪{u_iv_i+1,u_nv₁|i = 1,…,n - 1};V(Pⁿ) = {u,v,w,v₁,…,v_n}: E(Pⁿ) = [uv_i,vv_i,vw|i = 1,…,n)∪{v_iv_i+1i =1,…,n - 1}: and for u′_i∈S_n,v_i∈Pⁿ we make u′_iv_i∈H₁ (i=1,…,n):Then wehaveχ_at(H₁) = n+3.Theorem 2.2.4 Let H₂ be another u(S_n) expanding graph of Pⁿ. V(Pⁿ) ={u,v,w,v₁,…,v_n}:E(Pⁿ) = {uv_i,vv_i,vw|i = 1,…,n}∪{v_iv_i+1|i = 1,…,n-1}:V(S_n) = {v₁,…,v_n,u₁,…,u_n};E(S_n) = {v_iv_j,v_iu_i|i,j = 1,…,n}∪{u_iv_i+1,u_nv₁|i=1,…,n - 1}: and for v′_i∈S_n,v_i∈Pⁿ we make v′_iv_i∈H₂ (i = 1,…,n);Then we haveTheorem 2.2.5 Let H be a u(G) expanding graph of Pⁿ,V(G) = {u_i,…,u_n};V(Pⁿ) = {u,v,w,v₁,v₂,…,v_n}:E(Pⁿ) = {uv_i,vv_i,vw,(i = 1,2,…,n):v_iv_i+1(1 =1,…,n-1)} and for u_i∈G, v_i∈Pⁿ we make u_iv_i∈H. (i = 1,…,n);If G satisfy theconjecture of adjacent vertex-distinguishing total coloring thatχ_{at(G)≤△(G)+3: Then we haveχat(H)≤△(H) + 3.Theorem 2.3.1 Let G = (Pⁿ, uv1) + [(?)ⁿ, u′v′1}. Then we haveTheorem 2.3.2 Let G′= (Pⁿ,vv_n) + ((?)ⁿ,v′v′_n), Thenχ_at(G′) =â–³(G′) + 1.Theorem 2.3.3 Let H = (S_n, u₁v₁)+(S′_m,u′₁v′₁), Thenχ_at(H) = max{χ_at(S_n). Theorem 2.4.1 P_n is the graph of Path, when n≠3. P_n is a first class graph, then P_n[I₂] is a first graph. too.Theorem 2.4.2 F_n is the graph of Fan, then after dissecting, F_n satisfy thatχ_at(F_n[I₂]=χ_at(F_n[I₂]) + 1,(n≥4).Theorem 2.4.3 W_n is the graph of Wheel, then after dissecting, W_n satisfy thatχ_atW_n[I₂]) =χ_at(W_n[I₂]) + 1. (n≥4).Theorem 2.5.1 There are graphs S_n, C_n¹, C_n²,C_n³;We get a new graph H′from them with V(H′) = V(S_n)∪V{C_n¹)∪V(C_n²)∪V(C_n³) and E(H′) = E(S_n)∪E(C_n¹)∪E(C_n²)∪E(C_n³)∪(v_i¹v_i,v_i²u_i,v_i¹v_i| = 1,…,n;v_i^j∈C_n^j;u_i,v_i∈S_n}.Then we haveχ_at(H′) = n+4,(n≥4).Theorem 2.5.2 Let G₁ be the graph that satisfy u by P₂ of Pⁿ;that not only u′v_i∈E(G₁) but also u″v_i∈E(G₁),the vertices of P₂ are u′and u″;Then we haveTheorem 2.5.3 G is an arbitrary simple graph andâ–³(G)≥4. V(G) ={v₁,…,v_n}. we get a new graph H by the following operation:if v_iv_j∈E(G) thenwe add a new veterx u_k and adjact u_kv_i,u_kv_j;if G satisfy the conjecture of adjacent vertex-distinguishing total coloring thatχ_at(G)≤△(G) + 3. Then we haveχ_at(H)≤△(H)+3.