張東翰

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

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

1 定義及引理

定義1[1-2]設 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的一個正常全染色(簡記作k-PTC)，且稱數(shù) XT(G)=min｛k-STC｝為 G 的全色數(shù)。

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

定義3[6]蛛形圖Sk的頭點為v0，從v0出發(fā)有 k(k≥3)條路，每條路有 k 個點，共有 n（n=k2+1）個點，刪去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ù)。本文中未加述的術語、記號可在文獻[7]中找到。

2 定理及其證明

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

證明：因為△(Sk)=k,根據(jù)引理1可知XT(Sk)≥k+1,為了證明定理1成立只需給出一個（k+1）-PTC即可,設色集合 C={0，1，2,…,k}。對于點 v11,v12，…,v1k用色 2,1 循環(huán)染,對于點 v1i,vi2，…,vik,i=2,…,k,用色1,2循環(huán)染，對于v0點用色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)染；則此染色法為一個正常的全染色,所以此定理成立。

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

證明：因為△(Sk)=k,根據(jù)引理2可知Xst(Sk)≥2k+1,為了證明定理2成立只需給出一個（2k+1）-STC即可,設色集合 C={1，2，…,2k+1}。對于點 v11，v12，…,v1k用色k+1,3,4循環(huán)染；對于點v21,v22,…,v2k用色k+2,3,4循環(huán)染；對于點v31,v32,…,v1k,用色k+1,3,4循環(huán)染；對于點v21,v22,…,v2k用色k+2,3,4循環(huán)染；對于點v31,v32,…,v3k,用色k+3,4,5循環(huán)染；對于點v41,v42,…,v4k,用色 k+4,5,6 來染；對于點 vi1,vi2,…,vik,i=5,…,k用k+i,3,4循環(huá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)染；則此染色法為一個正常的星全染色,所以此定理成立。

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

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

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

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

[5]張 婷,強會英,李沐春.關于圖的星全染色[J].數(shù)學的實踐與認識,2008,38(18):160-163.

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

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