張東翰

(商洛學(xué)院 數(shù)學(xué)與計(jì)算科學(xué)系，陜西商洛 726000)

圖的染色是圖論中最著名和最古老的問題之一，由于其應(yīng)用的廣泛性使得越來越多的人對其進(jìn)行了研究,文獻(xiàn)[1-2]研究了一些特殊圖的全染色，文獻(xiàn)[3-5]研究了一些特殊圖的星全染色，文獻(xiàn)[6]討論了蛛形圖的一些染色問題。圖的全染色和星全染色是圖染色研究的熱點(diǎn)之一，并已經(jīng)取得了很多重要的結(jié)果。鑒于此，本文對蛛形圖的全染色和星全染色進(jìn)一步探討。

1 定義及引理

定義1[1-2]設(shè) G（V，E）是簡單圖，k 是自然數(shù)，f是從 V(G)∪E(G)到{1,2,3,…,k}的映射，如果滿足：

1)對任意的邊 uv∈E(G)，f（u）≠f（v）,f（u）≠f（uv）≠f（v）。

2)對任意的兩相鄰的邊uv，uw∈E(G)(v≠w),f（uv）≠f(vw)。

則稱f是圖G的一個(gè)正常全染色(簡記作k-PTC)，且稱數(shù) XT(G)=min｛k-STC｝為 G 的全色數(shù)。

定義2[3-5]圖G的一個(gè)k-正常全染色叫做k-星全染色（簡記為k-STC），如果圖G的任何路長為2的點(diǎn)和邊的著色均不相同，則稱Xst(G)=min{k|圖G的k-STC}為G的星全染色。

定義3[6]蛛形圖Sk的頭點(diǎn)為v0，從v0出發(fā)有 k(k≥3)條路，每條路有 k 個(gè)點(diǎn)，共有 n（n=k2+1）個(gè)點(diǎn)，刪去v0后，這k條路分別記為Pi=vi1，vi2，…，vik,(1≤i≤k),eij表示 Pi中連接 vi(j-1)和 vij(1≤i≤k,2≤j≤k)的邊，連接 v0和 vi1的邊記為 ei1(1≤i≤k)。

引理1[1-2]對于任意的簡單圖G都有XT(G)≥△(G)+1。

引理2[2-5]對于任意的簡單圖G都有是圖G的最大度，X'(G)是圖G的邊色數(shù)。本文中未加述的術(shù)語、記號可在文獻(xiàn)[7]中找到。

2 定理及其證明

定理1 設(shè)Sk是蛛形圖，則有XT(Sk)=k+1。

證明：因?yàn)椤?Sk)=k,根據(jù)引理1可知XT(Sk)≥k+1,為了證明定理1成立只需給出一個(gè)（k+1）-PTC即可,設(shè)色集合 C={0，1，2,…,k}。對于點(diǎn) v11,v12，…,v1k用色 2,1 循環(huán)染,對于點(diǎn) v1i,vi2，…,vik,i=2,…,k,用色1,2循環(huán)染，對于v0點(diǎn)用色0來染；對于邊v0v11,v0v21,…,v0vk1分別用色 1,2,…,k,來染；對于邊vi1vi2,vi2vi3,…,vi（k-1）vik,i=1,2,用色3,4循環(huán)染；對于邊 vi1vi2,vi2vi3,…,vi（k-1）vik,i=4,5,…,k，用色 3,4 循環(huán)染；對于邊 v31v32,v32v33,…,v3(k-1)v3k，用色 4，3 循環(huán)染；則此染色法為一個(gè)正常的全染色,所以此定理成立。

定理2設(shè)Sk是蛛形圖，則有Xst(Sk)=2k+1。

證明：因?yàn)椤?Sk)=k,根據(jù)引理2可知Xst(Sk)≥2k+1,為了證明定理2成立只需給出一個(gè)（2k+1）-STC即可,設(shè)色集合 C={1，2，…,2k+1}。對于點(diǎn) v11，v12，…,v1k用色k+1,3,4循環(huán)染；對于點(diǎn)v21,v22,…,v2k用色k+2,3,4循環(huán)染；對于點(diǎn)v31,v32,…,v1k,用色k+1,3,4循環(huán)染；對于點(diǎn)v21,v22,…,v2k用色k+2,3,4循環(huán)染；對于點(diǎn)v31,v32,…,v3k,用色k+3,4,5循環(huán)染；對于點(diǎn)v41,v42,…,v4k,用色 k+4,5,6 來染；對于點(diǎn) vi1,vi2,…,vik,i=5,…,k用k+i,3,4循環(huán)染，對于點(diǎn)v0用色2k+1來染；對于邊v0v11,v0v21,…,v0vk1分別用色1,2,…,k來染；對于邊v11v12,v12v13,…,v1(k-1)v1k用色2,1循環(huán)染；對于邊vi1vi2,vi2vi3,…,vi(k-1)vik,i=2,3,…,k用色1,i循環(huán)染；則此染色法為一個(gè)正常的星全染色,所以此定理成立。

[1]張東翰.路的廣義Mycielski的全染色[J].商洛學(xué)院學(xué)報(bào),2012,26(2):9-10.

[2]陳 亮.圖的全染色及鄰點(diǎn)可區(qū)別的全染色[D].重慶大學(xué),2007.

[3]馬慶媛,田雙亮.若干聯(lián)圖的星全染色[J].西北民族大學(xué)學(xué)報(bào),2010,31(4):16-18.

[4]強(qiáng)會(huì)英,李沐春,張忠輔.星和扇圖的廣義Mycielski的星全染色[J].蘭州理工大學(xué)學(xué)報(bào),2009,33(3):306-308.

[5]張 婷,強(qiáng)會(huì)英,李沐春.關(guān)于圖的星全染色[J].數(shù)學(xué)的實(shí)踐與認(rèn)識,2008,38(18):160-163.

[6]孫亮萍,強(qiáng)會(huì)英,孟利冬.蛛形圖的若干染色問題[J].蘭州交通大學(xué)學(xué)報(bào),2011,30(4):128-130.

[7]Bondy JA,Murty USR.Graph Theory with Applications[M].New York:The Macmillan Press Ltd,1976.