蛛形圖的全染色和星全染色

張東翰

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

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

1 定義及引理

定義1[1-2]設 G（V，E）是簡單圖，k 是自然數，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)，且稱數 XT(G)=min｛k-STC｝為 G 的全色數。

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

定義3[6]蛛形圖Sk的頭點為v0，從v0出發有 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的邊色數。本文中未加述的術語、記號可在文獻[7]中找到。

2 定理及其證明

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

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