若干合成圖的星全染色＊

王曉琦 田雙亮

（西北民族大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院 蘭州 730030）

0 引 言

本文所考慮的圖G均為有限無向簡單圖，用V（G），E（G）分別表示圖G的點和邊的集合.并用Δ（G）表示G的最大度.

定義1［1］簡單圖G和H 的合成圖是指具有頂點集V（G）×V（H）的簡單圖G［H］，它的頂點（u，v）和另一個頂點（u′，v′）相鄰當(dāng)且僅當(dāng)或者uu′∈E（G），或者u＝u′且vv′∈E（H）.

合成圖G［H］也可看成是若干個同構(gòu)于H的不相交圖關(guān)于G的等廣義聯(lián)圖［2］.特殊地，當(dāng)G為n階完全圖Kn，合成圖Kn［H］也可稱為n階完全圖Kn與H 的等多重聯(lián)圖［3］.

定義2 圖G的k－全染色是從V（G）∪E（G）到S＝｛1，2，…，k｝的一個映射σ，使得G 中沒有相鄰頂點或邊具有相同的像，且每個頂點與其關(guān)聯(lián)邊有不同的像.使G存在k－全染色的最小k值稱為G的全色數(shù)，記為χT（G）.

定義3 圖G的一個k－全染色σ被稱為k－星全染色，如果圖G中任意長為2的路的頂點和邊染不同顏色.即G中任意星上的頂點與邊染不同的顏色.使G存在k－星全染色的最小的k值稱為G的星全色數(shù)，記為χst（G）.

由定義3，容易得到以下引理：

引理1 對任意n階簡單圖G，n≥3，有2Δ（G）＋1≤χst（G）≤n＋χ′（G）.式中：χ′（G）為G的邊色數(shù).

引理2 對G的任意子圖H，有χst（H）≤χst（G）.

引理3 若G的直徑D（G）≤2，則在G的任一星全染色中，G的不同頂點必染不同的顏色.

在后面的討論中，需用到以下引理：

引理4 偶圖G的邊色數(shù)等于Δ（G）.

文獻［2］研究了一些等廣義聯(lián)圖（或合成圖）的Mycielski圖的星全染色，文獻［4－7］研究了完全圖與完全多部圖的Mycielski圖，以及輪，扇與路的廣義Mycielski圖的星全染色.本文將研究n＋1階輪，扇，星與m階簡單圖的合成圖的星全染色.文中未加說明的術(shù)語及符號可參見文獻［1］和［4］.

1 主要結(jié)果及其證明

設(shè)簡單圖G與H 的頂點集分別為V（G）＝｛ui｜i＝0，1，…，n｝與V（H）＝｛vi｜i＝0，1，…，m－1｝.在G［H］中，記wij＝（ui，vj），并令Vi＝｛（ui，vj）｜j＝0，1，…，m－1｝.由合成圖的定義，G［H］可表述為若干邊不交的子圖之并，即

式中：Gi，j為以（Vi，Vj）為二分類的完全偶圖，Hi表示以Vi為頂點集且同構(gòu)于H 的簡單圖.顯然，在G［H］中，有Gi，j?Km，m，且Hi與Hj是不相交的，其中i≠j，i，j＝0，1，…，n.下面研究當(dāng)G 為n＋1階輪Wn，扇Fn，或星Sn，且H 為m 階特殊圖時合成圖G［H］的星全染色.

設(shè)n＋1階輪Wn的頂點集與邊集分別為

其中ui＋1的下標(biāo)取模n，n≥4.

顯然，n＋1階扇Fn與星Sn可由Wn刪去若干條邊得到.

引理5 設(shè)G為n階簡單圖，n≥5.若Δ（G）＝2，則G存在n－星全染色，使得G的不同頂點染不同的顏色.

證明 不妨假設(shè)G是簡單連通圖.因Δ（G）＝2，所以G為n階圈或路.僅證明當(dāng)G為n階圈時引理結(jié)論成立，當(dāng)G為n階路時，可類似證明.

設(shè)G為n 階圈且G＝v0e0v1e1…vn－1en－1v0.設(shè)顏色集合為S＝｛0，1，…，n－1｝.現(xiàn)在定義如下一個從V（G）∪E（G）到S的映射σ：

顯然σ為G的n－星全染色，且使得G的不同頂點染不同色.因此，引理結(jié)論成立.

定理1 設(shè)G為n＋1階輪，扇，或星，且H為m 階簡單圖，其中n≥4，m≥5.若Δ（H）＝2，則χst（G［H］）＝（2n＋1）m.

證明 記G＊＝G［H］.顯然，G＊的直徑不超過2，即D（G＊）≤2.由引理3，在G＊的任一星全染色中，G＊的不同頂點必染不同的顏色，又因｜V（G＊）｜＝（n＋1）m，所以至少需要（n＋1）m 種顏色.另一方面，對任意邊uv∈E（Gn，i），i＝0，1，…，n－1，每一頂點ω∈V（G＊）＼｛u，v｝均與u或v相鄰，所以在G＊的星全染色σ中，的每一邊不能與G＊的任一頂點染相同的顏色.又因為是最大度為mn 的偶圖，由引理4知，）＝mn.所以，χst（G＊）≥（n＋1）m＋mn＝（2n＋1）m.又因為Sn?Fn?Wn，由引理2，χst（Sn［H］）≤χst（Fn［H］≤χST（Wn［H］）.因此，欲證χst（G［H］）≤2（n＋1）m，僅需證明當(dāng)G＊＝Wn［H］時，G＊存在（2n＋1）m－星全染色.

設(shè)顏色集合為S＝A∪B，且｜S｜＝（2n＋1）m，｜A｜＝ （n＋1）m，｜B｜＝nm.其中：A ＝；B ＝；｜Ai｜＝m；｜Bj｜＝m.現(xiàn)在分3步構(gòu)造G＊的染色σ：在式（1）中，首先用Ai中的m種顏色對Hi進行頂點染色，使得不同頂點染不同色，i＝0，1，…，n.其次，對i＝0，1，…，n，因為Hi?H及Δ（H）＝2，由引理5，可用Hi的頂點顏色對Hi的邊進行染色，使其成為Hi的m－星全染色.最后，用B中mn種顏色對∪uiuj∈E（G）Gi，j進行正常邊染色.具體地，因為Gi，j?Km，m，由引理4，可用Bi中的m 種顏色對Gn，i進行正常邊染色，用Bi＋2中的m種顏色對Gi，i＋1進行正常邊染色，其中Bi＋2的下標(biāo)與Gi，i＋1的第二個下標(biāo)i＋1取模n，其中i＝0，1，…，n－1.

容易看出，以上染色σ是G＊的（2n＋1）m－全染色，且在σ中，∪uiuj∈E（G）Gi，j的每一邊所染顏色與任意頂點所染顏色均不相同，并滿足G＊的不同頂點染不同的顏色.同時，σ限制在每一個Hi上均為Hi的星全染色，且不同的Hi所用的顏色集合不同.又因Hi與Hj是不相交的，其中i≠j，i，j＝0，1，…，n，所以在σ中，G＊的任意長為2的路的頂點和邊均染不同顏色，即σ是G＊的（2n＋1）m－ 星全染色.因此，χst（G＊）＝ （2n＋1）m.

定理2 設(shè)G為n＋1階輪，扇，或星，若H滿足χ′（H）＝Δ（H）＝m－1，其中n，m≥4，則χst（G［H］）＝2（n＋1）m－1.

證明 記G＊＝G［H］.由已知及引理1可得

由上式可知，若能證明χ′（G＊）≤（n＋1）m－1，則定理結(jié)論成立.又因Sn?Fn?Wn，由合成圖的定義，有G＊?Wn［H］.因此，僅需證明當(dāng)G＝Wn時，G＊存在（（n＋1）m－1）－正常邊染色.

假設(shè)G＝Wn，并設(shè)顏色集合S＝B∪C，且｜S｜＝（n＋1）m－1，｜B｜＝mn，｜C｜＝m－1，其中B＝，且｜Bj｜＝m，j＝0，1，…，n－1.

現(xiàn)在構(gòu)造G＊的邊染色σ：在式（1）中，首先用B中的nm 種顏色對 ∪uiuj∈E（G）Gij進行正常邊染色，染色方法與定理1證明中的第三步相同.其次，因χ′（H）＝m－1，所以可用C中的m－1種顏色對每一個Hi進行正常邊染色.

顯然，以上染色σ是G＊的（（n＋1）m－1）－正常邊染色.因此，定理結(jié)論成立.

2 結(jié) 論

由定理2可直接得到以下結(jié)論：設(shè)G為n＋1階輪，扇，或星，其中n≥4.若H滿足以下條件之一：（1）H 為m 階輪，扇，或星，其中m≥4；（2）H為偶階完全圖，則χst（G［H］）＝2（n＋1）m－1.

［1］BONDY J A，MURTY U S R.Graph theory with application［M］.New York：American Elsevier，1976.

［2］田雙亮.等廣義聯(lián)圖的Mycielski圖的星全染色［J］.山東大學(xué)學(xué)報：理學(xué)版，2009，45（6）：23－26，34.

［3］田雙亮，陳 萍.若干多重聯(lián)圖的邊染色［J］.南開大學(xué)學(xué)報：自然科學(xué)版，2007，40（3）：27－30.

［4］YAP H P.Total colorings of graphs［M］.New York：Springer Verlag，1996.

［5］李沐春，強會英，張忠輔.完全圖和完全多部圖的Mycielski圖的星全染色［J］.福州大學(xué)學(xué)報：自然科學(xué)版，2009，37（2）：180－183.

［6］強會英，李沐春，徐保根，等.輪和路的廣義Mycielski圖的星全染色［J］.蘭州理工大學(xué)學(xué)報，2008，34（4）：145－147.

［7］強會英，李沐春，張忠輔.星圖和扇圖的廣義Mycielski圖的星全染色［J］.江西師范大學(xué)學(xué)報：自然科學(xué)版，2009，33（3）：306－308.