A New Result On AVDT Chromatic Number Of Planar Graphs

Let φ be a total coloring of G,and let u be a vertex of G.We use Cφ(u)to denote the set of colors received by u or the edges incident with u under φ,and call Cφ(u)the set of colors of u with respect to φ.An adjacent vertex distinguishing total coloring(an AVD total coloring for short)of a graph G is a proper total coloring of G such that any pair of adjacent vertices have distinct sets of colors.The adjacent vertex distinguishing total chromatic number χa"(G)is the smallest integer k such that G has an AVD total coloring with k colors.Zhang et al.([13])proposed the following conjecture:For any graph G with at least two vertices,χa"(G)≤ △(G)+ 3.In[5],Huang and Wang proved the following theorem:For planar graphs G with △(G)≥11,χa"(G)≥△(G)+ 3.Cheng et al.([5])improved the result and showed that for planar graphs G with △(G)≥ 10,χa”(G)≤ △(G)+ 3.In[7],Huang and Wang characterized completely the AVD total chromatic num-ber of planar graphs G with △(G)≥ 14,they proved the following theorem:If G is a planar graph with △(G)≥ 13,then χa"(G)≤ △(G)+ 2;If G is a planar graph with△(G)>14,then χa"(G)= △(G)+ 2 if and only if G contains two adjacent vertices of degree △(G).In this thesis,we will improve the bound of Huang and Wang.In pre-cise,we have the following conclusion:If G is a planar graph with △(G)≥ 12,thenχa"(G)≤ △(G)+ 2;If G is a planar graph with △(G)>13,then χa"(G)=△(G)+ 2 if and only if G contains two adjacent vertices of degree △(G).