几类图的均匀邻点可区别全染色

On the Equitable Adjacent-Vertex-Distinguishing Total Coloring of Graphs of Some Classes

邻点可区别全染色是在正常全染色的定义下,使得任两相邻顶点的色集不同。设G(V,E)为一个简单图,f为G的一个k-邻点可区别全染色,若f满足||Vi∪Ei|-|Vj∪Ej||≤1(i≠j),其中,Vi∪Ei={v|f(v)=i}∪{e|f(e)=i},记C(i)=Vi∪Ei,则称f为G的k-均匀邻点可区别全染色,简记为k-EAVDTC,并称χeat(G)=min{k|G存在k-均匀邻点可区别全染色}为G的均匀邻点可区别全染色数。本文给出了路、圈、风车图Kt3、图Dm,4和齿轮图W軜n的均匀邻点可区别全染色,以及它们的均匀邻点可区别全色数的确切值。

With the definition of proper total coloring of a graph, an Adjacent Vertex-Distinguishing Total Coloring （AVDTC） means that none of the two adjacent vertices are incident with the same set of colors. The concept of the AVDTC is proposed by Zhongfu Zhang （2004）, and the AVDTC of graphs such as path, cycle, complete graph, complete bipartite graph, star and tree are discussed in Zhang＇s paper. The AVDTC of Pm×Pn, Pm×Cn, Cn×Cn are also given where Pm, Cn are a denoted path with order m and a circle with order n, respectively; the AVDTC of Mycielski graph of some graphs such as path, circle and so on are given in another Zhang＇s paper （2000）. For the adjacent vertex-distinguishing total chromatic number, a conjecture is given in Zhang＇s paper （2004）. Let G （V, E） be a simple connected graph of order n （n≥2）, k be a natural number and f be a k-adjacent vertex-distinguishing total coloring of graph G. If f satisfies the condition ｜｜Vi∪Ei｜-｜Vj∪Ej｜｜≤1（i≠j）, where Vi∪Ei={v｜f（v）=i}∪{e｜f（e）=i},C（i）=Vi∪Ei, then f is called an equitable adjacent vertex-distinguishing total coloring of graph G （k-EA VDTC） and χeat（G）=min{k｜G has k-EAVDTC） is called the chromatic number of the equitable adjacent-distinguishing total coloring of graph G. This paper gives the equitable adjacent vertex distinguishing total coloring chromatic number of path Pn and cycle Cn and graph K3^1 andgraph Dm4 and gear wheel Wn^~.