蛛形圖的全圖和中心圖的均勻染色＊

趙金麗， 卜月華

(浙江師范大學數理與信息工程學院，浙江金華 321004)

用V(G)和E(G)分別表示圖G的頂點集和邊集．稱映射φ:V(G)→{1，2，…，k}為圖G的一個正常k-染色，如果φ使得V(G)中任何2個相鄰的頂點u，v，φ(u)≠φ(v);稱χ(G)為最小的顏色數k，使得圖G 有正常 k-染色［1］．如果 G 的頂點集合可以剖分成 k 個獨立集 V1，V2，…，Vk，使得||Vi|-|Vj||≤1(i≠j)成立，則稱圖G是k-均勻可染的，(V1，V2，…，Vk)稱為一個均勻獨立集剖分．使得圖G均勻k-可染的最小的整數 k 為圖 G 的均勻色數，記為 χEq(G)［2］．顯然，χEq(G)≥χ(G)．

給定一個圖G=(V，E)，對圖G每一條邊分割1次，即在每條邊上插入一個頂點，連接所有在G中不相鄰的頂點．對圖G進行這樣的操作后所得到的圖稱為G的中心圖，記為C(G)．

給定一個圖G，定義圖G的全圖T(G)如下:T(G)的頂點集合為V(G)∪E(G)，T(G)中滿足下面條件之一的2個頂點x，y相鄰:

1)x，y∈V(G)以及 x，y在 G 中相鄰;

2)x，y∈E(G)以及 x，y在 G 中相鄰;

3)x∈V(G)，y∈E(G)，x，y在 G 中關聯．

一個圖G稱為是一個蛛形圖［3］，若G是一棵樹且至多存在一個度數大于2的頂點v，頂點v稱為頭點．蛛形圖有時也稱為廣義星圖．

對于一些特殊圖的全圖和中心圖的均勻染色，Ali Akbar等［4］撰文進行了討論，得到了如下結果:

定理1［4］路Pn的全圖的均勻色數 χEq［T(Pn)］=3．

定理 2［4］對于圈 Cn，若 n≡0(mod 3)，則 χEq［T(Cn)］=3．

而當n不能被3整除時，其均勻色數的情況仍不清楚．

定理 3［4］星圖 K1，n的中心圖的均勻色數 χEq［C(K1，n)］=n．

定理 4［4］等完全二部圖 Kn，n(n≥3)的中心圖的均勻色數 χEq［C(Kn，n)］=n．

定理5［4］完全圖Kn(n≥4)的中心圖的均勻色數 χEq［C(Kn)］=3．

有關均勻染色的其他結果可參考文獻［5］．

本文討論了蛛形圖的全圖和中心圖的均勻染色問題，得到了蛛形圖的全圖的均勻色數(定理6)和蛛形圖的中心圖的均勻色數(定理7)．

定理6 設G是一個蛛形圖，刪去頭點后共有n(n≥3)條路，該n條路記為Pi(1≤i≤n)，且|Pi|=n-1，則 χEq［T(G)］=n+1．

證明 設蛛形圖G的頭點為v，刪去v后，把該n條路分別記為Pi=vi1vi2…vin(1≤i≤n)，eij表示Pi中連接 vi(j-1)和 vij(1≤i≤n，2≤j≤n)的邊，連接 v 與 vi1的邊記為 ei1(1≤i≤n)．NT(G)(vij)表示點 vij在T(G)中的鄰域．

根據全圖的定義，有:

因 T(G)是包含由 v，e11，e21，…，en1的 n+1 個頂點所構成的完全子圖，故 χEq［T(G)］≥χ［T(G)］≥n+1．另一方面，若能夠證明頂點集合V［T(G)］可以劃分成n+1個獨立集，且任意2個獨立集之間的元素個數至多相差1，則有 χEq(［T(G)］)≤n+1．

為了證明方便，分n≤6和n≥7兩種情況來證明．當n≤6時，具體給出每個獨立集的元素，從而證明 χEq(［T(G)］)=n+1．

1)n≤6．

①n=3．令:T1={e11，v21，v23，v31，v33};T2={e21，v13，e12，e32，v22};T3={v11，e13，e22，v32，e31};T4={v，v12，e23，e33}．Ti(i=1，2，3，4)是元素個數分別為 5，5，5，4 的獨立集，此獨立集剖分滿足條件“任意獨立集之間的元素個數至多相差1”．

②n=4．令:T1={v13，e11，v21，v31，e33，v41};T2={v23，e21，e14，e34，v42，e44};T3={v33，e31，e12，v24，e22，v44，e42};T4={v11，e13，v22，e24，e32，v43，e41};T5={v，v12，e23，v32，e43，v14，v34}．Ti(i=1，2，3，4，5)是元素個數分別為6，6，7，7，7的獨立集，此獨立集剖分滿足條件“任意獨立集之間的元素個數至多相差1”．

③n=5．令:T1={e11，v21，v31，e33，v41，v51，e53，v44};T2={v24，e21，e14，e34，v42，e44，v52，e54};T3={e31，v13，e15，v23，v43，v53，e55，v11};T4={e41，v15，e12，v25，e22，v35，e32，v55，e52};T5={v54，e51，e13，v22，e24，v33，e35，v45，e42};T6={v，v14，e23，e43，v12，v32，v34，e25，e45}．Ti(i=1，2，3，4，5，6)是元素個數分別為 8，8，8，9，9，9 的獨立集，此獨立集剖分滿足條件“任意獨立集之間的元素個數至多相差1”．

④n=6．同理成立(略)．

2)n≥7．令:Vij={vij，ei(j+2)}，1≤j≤n-2;Vi(n-1)={vi(n-1)，ei1};Vin={vin，ei2}．其中 1≤i≤n．每個Vij(1≤i，j≤n)的元素個數都為2，共有n2個集合，每個集合在T(G)中都是獨立集，現在用這些集合繼續構造n個獨立集．令:

至此，上述n2個集合Vij(1≤i，j≤n)合并為n個獨立集，每個獨立集的元素個數均為2n，則還剩下頭點v沒包括進去，從T1到Tn-1中分別選取2個不與頭點v相鄰的、且彼此也都不相鄰的頂點，共同構成Tn+1．此時分2種情況:

①n為奇數．在每個Ti(1≤i≤n-2)中選取2個頂點，取法如下:

當i是奇數時，在Ti中選取頂點e2(i+2)，e(n-1)(i+2);當i是偶數時，在 Ti中選取頂點v1i，v(n-2)i．然后再在Tn-1中選取頂點v1n，v(n-2)n．所選取的2(n-1)個頂點互不相鄰．令:

②n為偶數．在每個Ti(1≤i≤n-2)中選取2個頂點，取法如下:

當i是奇數時，在Ti中選取頂點e2(i+2)，e(n-1)(i+2);當i是偶數時，在Ti中選取頂點v1i，v(n-2)i．然后再在Tn-1中選取頂點e32，e42．所選取的2(n-1)個頂點互不相鄰．令:

定理7 設G是一個蛛形圖，刪去頭點后共有n(n≥3)條路，該n條路記為Pi(1≤i≤n)，且|Pi|=

證明 記v為蛛形圖G的頭點，刪去v后，把該n條路分別記為Pi=vi1vi2… vin，1≤i≤n，在C(G)中，vi(j-1)與 vij之間插入的頂點記為 uij(1≤i≤n，1≤j≤n)．其中:vi0=v;NC(G)(vij)表示點 vij在 C(G)中的鄰域．根據中心圖的定義，有:

因為原圖中不相鄰的頂點在中心圖C(G)中相鄰，所以C(G)中的每個獨立集至多含V(G)中的2個頂點，且只能是在G中相鄰的2個頂點．下面根據n的不同情況進行討論．

此時，有|Vi1|=3(2≤i≤n)，|Vi((n+1)/2)|=3(1≤i≤n)，|V11|=4，|Vij|=4(1≤i≤n，2≤j≤(n-1)/2)滿足均勻染色的條件，所以當n=2k+1時，χEq［C(G)］=(k+1)n=(k+1)×(2k+1)=2k2+3k+1．定理7證畢．

關于確定圖的全圖和中心圖的均勻色數的文獻還非常少，可以繼續研究的問題依然很多，如:

問題1 在定理6和定理7中的蛛形圖刪去頭點后路長為l(l≠n-1)的情況下，其全圖和中心圖的均勻色數為多少?

問題2 其他結構稍復雜的圖類，如二叉樹等，其全圖和中心圖的均勻色數為多少?

［1］卜月華．圖論及其應用［M］．南京:東南大學出版社，2000:198-199．

［2］Zhu Junlei，Bu Yuehua．Equitable list coloring of planar graphs without short cycles［J］．Theoretical Comput Sci，2008，407(1/2/3):21-28．

［3］Marek Kubale．Graph Colorings［M］．Rhode Island:American Mathematical Society，2004:139-144．

［4］Ali Akbara M M，Kaliraja K，Vernold Vivinb J．On Equitable Coloring of Central Graphs and Total Graphs［J］．Electronic Notes in Discrete Mathematics，2009，33(1):1-6．

［5］朱俊蕾，卜月華．圖 Pn∨Km，n的均勻全色數［J］．浙江師范大學學報:自然科學版，2007，30(1):58-64．