The Adjacent Vertex-distinguish Total Coloring Of Graphs

The coloring problem and some other graph theories are all from the study of the celebrated four color problem.In the combinatorial mathematics and our living,the coloring problem has a big application,and with the development of the field some scholars presented and studied a. few coloring problems with different restriction.A (proper)k-coloring of graph G [1] is an assignment of one of k colors to each vertex in such a way that adjacent vertices have distinct colors.Define the chromatic number of G asχ(G) = min{k|graph G has k-colorings}.Similar,a (proper)k-edge-coloring of graph G is an assignment of one 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 total coloring is a generalization of the coloring and the edge coloring,all of the elements (verteics and edges) of the graph are colored in such a way that no two adjacent or incident elements are colored the same.It's a traditional coloring problem and was introduced by Vizing(1964) and independently Behzad(1965) with total coloring conjecture[23,24,25].The vertex-distinguishing total coloring and the adjacent vertex-distinguishing total coloring are two new coloring problem and were presented by Zhongfu Zhang with two conjecture resentely.Definition Suppose G(V(G), E(G)) is a graph,k is a positive integer and S is a k-element set.Let f be a map from V(G)∪E(G) to S.If1).for any uv,vw∈E(G),u≠w,there is f(uv)≠f{vw);2).for any uv∈E(G),there are f(u)≠f(v),f(u)≠f(uv),f(uv)≠f(v). then f is called a k-total coloring of graph G and the total-chromatic number is defined asχ_t(G)(or denoted asχ″(G)) = min{k|graph G has k-total-colorings}.If f also satisfies 3).for any u,v∈V(G),there is C(u)≠C(v);where C(u) = {f{u)}∪{f{uv)|uv∈E(G)} is called the color set of vertex u.then f is called a vertex-distinguishing k-total coloring of graph G(briefly noted as k-VDTC) andχ_vt(G) = min{k|G has k-VDTC} is called vertex-distinguishing total chromatic number of graph G.If condition 3) is changed to3′).for any uv∈E(G),there is C(u)≠C(v).then f is called a adjacent vertex-distinguishing k-total coloring of graph G(in brief,noted as k-AVDTC) andχ_at(G) = min{k|G has k-AVDTC} is called the adjacent vertex-distinguishing total chromatic number of graph G.Total Coloring Conjecture For any simple graph G,χ_T(G)≤△(G) + 2.Vertex-Distinguishing Total Coloring Conjecture For any simple graph G,k_T(G)≤χ_vt(G) < k_T(G) + 1,where k_T(G) = min{l|C_l^d+1≥n_d,δ≤d≤△, n_d is the number of the vertices with degree d in graph G}.Adjacent Vertex-Distinguishing Total Coloring Conjecture For anysimple graph G,χ_at(G)≤△(G) + 3.Zhang Zhongfu presented two important results about the adjacent vertex-distinguishing total chromatic number of graph G.For any simple connected two important graph G of order n(n≥2),adjacent vertex-distinguishing total chromatic numberχ_at(G) exsits,andχ_at(G)≥△(G) + 1.If G(V,E) has two adjacent maximum degree vertices,thenχ_at(G)≥△(G)+2.The problem of determining the total chromatic number of a graph is NP-hard,and we obtain some resultes for a lot of graph classes and graphs with certain conditions in this field.So far,the studies of the vertex-distinguishing total coloring and the adjacent vertex-distinguishing total colorings are for the special graphs,for example:Mycielski graphs and the Cartesian product graphs . We briefly summerize our main results as follow:Let s,l∈N and 1≤l≤s, the generalized graph Petersen P(s, l) has vertex set V:={v₀,v₁,…, v_s-1,w₀,w₁,…, w_s-1},and edge set E:={v_iv_i+1|i= 0.1,…, s-2}∪{v_s-1v₀}∪{v_iw_i}i = 0,1,2,…, s-1}∪{w_iw_j:|i-j|_s=l} in which |i -j|_s≡|i - j|(mod s).Theorem 2.1.1 For generalized graph Petersen P(s,l) . if s > 2l,l≠12k,k = 1,2,…, thenχ_at(P(s,l) = 5.The following results are about the generalized adjacent vertex-distinguishing total coloring of the generalized graph Petersen P(s,l) . For generalized graph Petersen P(s,l),C = v₀v₁,…, v_s-1 is a cycle .Let C′= v′₀v′₁…v′_s-1 and C″= v″₀v″₁…v″_s-1 are two copies of C. Graph G can be obtained by application of the following operation : join v_i,v′_i and v_′i,v″_i i=0,1,…,s-1.Lemma 2.1.2 Graph G is defined as we just said ,thenχ_at(G) = 6.Theorem 2.1.3 For generalized graph Petersen P(s,l), cycle C=v₀v₁…v_s-1 has m copies. joint v_i^s,v_i^t when |s-t|=1,0≤s,t≤m.so that we can obtain a new graph G.andχ_at(G) = 6.Let G₁ and G₂ be disjoint k-critical graphs (k≥4).For i = 1,2,let H_i be a complete 2-graph in G_i.For i = 1,2,let y_i be a vertex of G_i - H_i joined to a vertex x_i of H_i.Obtain G from G₁ and G₂ by identifying H₁ and H₂ to a new complete 2-graph H so that x₁ and x₂ are identified, delete the edges x_iy_i and join y₁ and y₂ by a new edge[14].Let W_n = K₁?C_n, V(W_n) = {v₁,v₂,…,v_n, v₀}, E(W_n) = {v_iv_i+1|i = 1,…,n; v(n+1) = v₁}∪{v₀v_i|i = 1,…, n}, in which W′_n is a copy of W_n.Theorem 2.2.1 Generalized Hajós sum W^*_n = (W_n, v₁v₂) + (W′_n, v′v′₂), identify v₁v₂, v′₁v′₂ to a new edge ,remove v₂v₃, v′₂v′₃,and joint v₃, v′₃, thenTheorem 2.2.2 Generalized Hajós sum W_n^* = (W_n,v₀v₁) + (W′_n,v′₀v′₁), identify v₀v₁,v′₀v′₁ to a new edge ,remove v₁v₂,v′₁v′₂,and joint v₂, v′₂,thenTheorem 2.2.3 Generalized Hajós sum W_m,n^* = (W_m,v₁v₂) + (W′_n,v′₁v′₂), identify v₁v₂,v′₁v′₂ to a new edge ,remove v₂v₃.v′₂v′₃,and joint v₃,v′₃, thenTheorem 2.2.4 Generalized Hajós sum, G = (K_n, v_n-1v_n) + (K′_m, v′_m-1v′_m), m,n≥4, identify v_n-1v_n, v′_m-1v′_m to a new edge,remove v_nv₁, v′_mv′₁,and joint v₁, v′₁, then Theorem 2.3.1 For graph P_n^k. if k > 1. n≥2k + 2.thenχ_at(P_n^k) = 6.The following results are about K(n, m).Graph Kesern K(n, m) (1) has vertices all the m-subsets of a set W = {a₁, a₂,…,a_n} the vertic u is denoted by (a_i1,a_i2,…,a_im),i₁,i₂,…, i_m∈{1,2,…, n}:(2) for e = uv,e in E,a_i1,a_i2,…,a_im, a′_i1,a′_i2,…,a′_im in u = (a_i1,a_i2,…,a_im),v = (a′_i1,a′_i2,…,a′_im) are all diffrents.Theorem 2.4.1χ_at(K)5,2)) = 5.Theorem 2.4.2χ_at(K(6,2)) = 8.Theorem 2.4.3χ_at(K(7.2)) = 11.