徐曉青 李雙元 張衛(wèi)平

摘要：設(shè)f是圖G的一個(gè)正常的k-全染色，若G中任意兩點(diǎn)的色集不同，則稱f為G的k-點(diǎn)可區(qū)別全染色，簡記為k-VDTC of G,，并稱最小的k為G的點(diǎn)可區(qū)別全色數(shù)。該文針對(duì)完全圖的點(diǎn)可區(qū)別全染色的特點(diǎn)提出了分類順次著色算法，該算法首先按照一定的規(guī)則對(duì)元素進(jìn)行分類然后對(duì)元素進(jìn)行順次著色，同時(shí)給出關(guān)聯(lián)鎖表，根據(jù)關(guān)聯(lián)鎖表判斷是否得到問題的解。實(shí)驗(yàn)結(jié)果表明：該算法有效地解決了完全圖的點(diǎn)可區(qū)別全染色問題。

關(guān)鍵詞：k-點(diǎn)可區(qū)別全染色；點(diǎn)可區(qū)別全色數(shù)；分類順次著色；完全圖；關(guān)聯(lián)鎖表

中圖分類號(hào)：TP18文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1009-3044(2012)18-4498-03

Algorithm for the Vertex-Distinguishing Total Coloring of Complete Graphs

XU Xiao-qing, LI Shuang-yuan, ZHANG Wei-ping

(Lanzhou Jiaotong University,Lanzhou 730070,China)

Abstract: Let f be a proper k- total coloring of a graph G , if for any two distinct vertices u and v in G,the set of colors of u differs from the set of colors of v, f is called a k-vertex distinguishing total coloring of G , is abbreviated k-VDTC of G and the minimal number k of colors required for vertex-distinguishing total coloring of G is called the vertex-distingishing total chromatic number of G.In this paper, a new algorithm whose name is algorithm of classified order coloring is proposed on the base of the characteristics of the vertex-distinguish? ing total coloring of complete graphs .All of its elements are classified according to some rules and then are colored in proper sequence in the algorithm. Moreover, a relatelocktable is presented to judge whether the result is correct. The experimental results show that the algo? rithm can effectively solve the vertex-distinguishing total coloring of complete graphs.

Key words: vertex-distinguishing total coloring; vertex-distinguishing total chromatic number; classified order coloring; relatelocktable

該文根據(jù)完全圖的點(diǎn)可區(qū)別全染色的特點(diǎn)，設(shè)計(jì)了聚類順次著色的算法，利用關(guān)聯(lián)鎖表和元素的2次冪求和對(duì)算法進(jìn)行控制，使得算法有效的解決了完全圖的點(diǎn)可區(qū)別全染色。

[1] ZHANG Zhong-fu, QIU Peng-xiang, XU Bao-gen, et al. vertex-distinguishing toal coloring of graphs[J]. Ars Com, 2008, 87:33-45.

[2] BURRIS A C, SCHELP R H. Vertex-distinguishing proper edge-colorings[J]. Journal of Graph Theory, 1997, 26(2): 73-82.

[3] BALISTER P N, GYORI E,LEHEL J, et al. Adjacent vertex distinguish edge-colorings[J]. Journal on Discrete Mathematics, 2007, 21(1): 237-250.

[4] HATAMI H.Δ+300 is a bound on the adjacent vertex distinguishing edge chromatic number[J]. Journal of Combinatorial Theory(Series B), 2005, 95(2): 246-256.

[5] ZHONG Zhong-fu, LIU Lin-zhong, WANG Jian-fang. Adjacent strong edge coloring of graphs[J]. Appl Math Lett, 2002, 15(5): 623-626.

[6]張忠輔,李敬文,陳祥恩，等.圖的距離不大于β的任意兩點(diǎn)可區(qū)別邊染色[J].中國科學(xué),2006,49(3): 703-708.

[7]張忠輔,李敬文,陳祥恩,等.圖的距離不大于β的任意兩點(diǎn)可區(qū)別全染色[J].中國科學(xué),2006,49（10): 1430-1440.

[8] BONDY J A, MARTY U S R. Graph theory with application[M]. New York:The Macmillan Press Ltd, 1976.

[9] ZHANG Zhong-fu, CHEN Xiang-en, LI Jing-wen,et al. On adjacent-vertex-distinguishing total coloring of graphs[J]. Sci China(Ser A), 2005, 48(3):289-299.