若干圖的廣義字典積的全染色

田雙亮，孫向濤

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

0 引言

本文所考慮的圖G都是有限無向的簡單圖，用V（G），E（G）分別表示G的點和邊的集合.并用Δ（G）表示G的最大度.本文未給出的其他定義可參考文獻(xiàn)［1］.

定義1［2］設(shè)G 是具有頂點集V（G）＝｛t1，…，tn｝，n≥2的圖，hn＝（Hi）i∈｛1，2，…，n｝是頂點不相交圖的序列，其中圖 Hi的頂點集為V（Hi）＝｛（ti，y1），…，（ti，yx）｝，x≥1.稱G［hn］為G 與hn＝（Hi）i∈｛1，2，…，n｝的廣義字典積，其中G［hn］的頂點集為V（G［hn］）＝∪ni＝1V（Hi），且兩個頂點（ti，yp）與（tj，yq）相鄰當(dāng)且僅當(dāng)ti＝tj且（ti，yp）（ti，yq）∈E（Hi），或（ti，tj）∈E（G）.若 Hi?H 對于i＝1，2，…，n，則G［hn］記為G［H］，且稱G［H］為G與H的字典積.

兩個頂點不相交圖G1與G2的聯(lián)圖［1］是指在G1與G2的并圖中，把G1的每個頂點和G2的每個頂點連接起來所得到的圖，記為G1∨G2.由廣義字典積的定義知，聯(lián)圖G1∨G2是2階路P2與h2＝（G1，G2）的廣義字典積P2［h2］.G 與hn＝（Hi）i∈｛1，2，…，n｝的廣義字典積G［hn］也可稱為不相交圖 H1，H2，…，Hn關(guān)于G 的廣義聯(lián)圖［3］.G與H 的字典積G［H］可稱為H關(guān)于G的等廣義聯(lián)圖.完全多部圖可看成是若干零圖的關(guān)于完全圖的廣義聯(lián)圖，而多重聯(lián)圖［4］則可看成是若干個圖關(guān)于完全圖的廣義聯(lián)圖.

圖G的一個全染色［5］σ是從V（G）∪E（G）到C的映射，且滿足條件：（1）沒有相鄰的兩條邊或兩個頂點具有相同的像；（2）G的每個頂點v的像與v關(guān)聯(lián)的邊的像不同.若σ∶V（G）∪E（G）→C是G的全染色，且｜C｜＝k是一個整數(shù)，則稱G是可k-全染色的.使G可k-全染色的最小的k值，稱為G的全色數(shù)，記為χT（G）.

1965年，Behzad在文獻(xiàn)［5］中提出了全染色的概念，研究了一些特殊圖類的全色數(shù)，在此基礎(chǔ)上提出了圖的全色數(shù)猜想：對任意的圖G，有χT（G）≤Δ（G）＋2.文獻(xiàn)［5-7］研究了圖的全染色.本文主要研究一些特殊圖的廣義字典積G［hn］的全染色.在后面的討論中要用到以下引理：

引理1［5］對圖G 的任意子圖H，有χT（H）≤χT（G）.

由引理1與引理2，對任意n階簡單圖H，若n為奇數(shù)，則H的全色數(shù)不超過n；若n為偶數(shù)，H的全色數(shù)不超過n＋1，且對H的任一（n＋1）-全染色，n＋1種顏色中必存在一種顏色c，使得H的所有頂點均不染顏色c.

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

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

n階扇Fn與星Sn分別可由輪Wn刪去一些邊得到.為敘述方便，令V（Hi）＝｛（ti，yj）｜j＝1，2，…，m｝，并記vij＝（ti，yj）.在G［hn］中，用Gkl表示具有二分類（V（Hk），V（Hl））的m-正則二部圖.

下面我們研究G 為輪Wn，或扇Fn，或星Sn時廣義字典積G［hn］的全色數(shù)，其中hn＝（Hi）i∈｛0，1，…，n-1｝，n≥5，Hi為m 階簡單圖，i＝0，1，…，n-1.

若G是n階的輪即G＝Wn，由圖的廣義字典積的定義，我們可將圖G［hn］分解為三個邊不交子圖G（1），G（2）與G（3），即

定理1 設(shè)G 為n 階輪，或扇，或星，其中n≥5.在hn＝（Hi）i∈｛0，1，…，n-1｝中，｜Hi｜＝m 對于i＝0，1，…，n-1.若H0為m 階完全圖的補(bǔ)圖，則χT（G［hn］）＝（n-1）m＋1.

證明 顯然，χT（G［hn］）≥Δ（G［hn］）＋1＝（n-1）m＋1.因此，需證明χT（G［hn］≤（n-1）m＋1.因Fn與Sn均為Wn的子圖，所以Sn［hn］?Fn［hn］?Wn［hn］.由引理1，僅需證明，當(dāng)G＝Wn時，χT（G［hn］）≤（n-1）m＋1.

首先，對G（1）進(jìn)行正常全染色.由引理1與引理2，可用Ci-1∪｛a｝中的m＋1種色對Hi進(jìn)行正常全染色，使得Hi的所有頂點均不雜顏色a，其中i＝1，2，…，n-1.并用顏色a染H0的每一頂點.

其次，對G（2）進(jìn)行正常邊染色.用Ci（下標(biāo)取模n-1）中m種顏色對m-正則二部圖G0i進(jìn)行正常邊染色，其中i＝1，…，n-1.

最后，對G（3）進(jìn)行正常邊染色.用Ci＋2（下標(biāo)取模n-1）中m 種顏色對m-正則二部圖Gi，i＋1進(jìn)行正常邊染色，其中i＝1，2，…，n-2.并用C2的m 種顏色對m-正則二部圖Gn-1，1進(jìn)行正常邊染色.

容易看出，以上染色σ是G［hn］的一個（（n-1）m＋1）-正常全染色，所以有χT（G［hn］）≤（n-1）m＋1.因此，定理結(jié)論成立.

定理2 設(shè)G 為n 階輪，或扇，或星，其中n≥5.在hn＝（Hi）i∈｛0，1，…，n-1｝中，｜Hi｜＝m 對于i＝0，1，…，n-1.若H0為m 階完全圖，則χT（G［hn］）＝mn.

證明 顯然，χT（G［hn］）≥Δ（G［hn］）＋1＝mn.與定理1的證明類似，僅需證明，當(dāng)G＝Wn時，有χT（G［hn］）≤mn.

情況1 m 為奇數(shù).在G［hn］中，G（2）與G（3）的染色與定理1證明中的染色相同.由引理1與引理2，可用Ci-1中的m種顏色對Hi進(jìn)行正常全染色，其中i＝0，1，…，n-2；用Cn-1中的m種顏色對H0進(jìn)行正常全染色.顯然，以上染色為G［hn］的一個mn-正常全染色.

情況2 m 為偶數(shù).在G［hn］中，G（2）-E（G01）與G（3）的染色與定理1證明中的染色相同.由引理1與引理2，可用Ci-1∪｛cn-1，0｝中的m＋1種顏色對 Hi進(jìn)行正常全染色，使得 Hi的所有頂點均不染顏色cn-1，0，其中i＝2，3，…，n-1；并用C0∪｛c1，0｝中的m＋1種顏色對H1進(jìn)行正常全染色，使得H1的所有頂點均不染顏色c1，0.然后，用Cn-1∪｛c1，0｝的m＋1種顏色對H0進(jìn)行正常全染色，使得H0的所有頂點均不染顏色c1，0，具體地，當(dāng)k＋l≠m＋1時，令

顯然，在 H0的染色中，顏色cn-1，k-1不在頂點v0k上表現(xiàn)，所以可取G01的一個完美匹配 M＝｛v0kv1k｜k＝1，2，…，m｝，并用顏色cn-1，k-1染邊v0kv1k，其中k＝1，2，…，m.因G01-M 為（m-1）-正則二部圖，所以可用C1-｛c1，0｝中的m-1種顏色對G01-M 進(jìn)行正常邊染色.

容易看出，以上染色是G［hn］的一個mn-全染色，所以有χT（G［hn］）≤mn.因此，定理結(jié)論成立.

定理3 設(shè)G 為n 階輪，或扇，或星，其中n≥5.在hn＝（Hi）i∈｛0，1，…，n-1｝中，｜Hi｜＝m 對于i＝0，1，…，n-1.若H0是m 階二部圖，且Δ（H0）≥2，則χT（G［hn］）＝Δ（H0）＋（n-1）m＋1.

證明 設(shè) H0具有二分類（X，Y），且記Δ0＝Δ（H0）.顯然，χT（G［hn］）≥Δ（G［hn］）＋1＝Δ0＋（n-1）m＋1.與定理1的證明類似，我們僅需證明，當(dāng)G＝Wn時，χT（G［hn］）≤Δ0＋（n-1）m＋1.

首先，對G（1）進(jìn)行正常全染色.因H0是具有最大度Δ0的二部圖，所以可用顏色a0染X中的每一頂點，用顏色a1染Y 中的每一頂點，并用Cn-1∪｛c1，0｝中其他Δ0種顏色對 H0進(jìn)行正常邊染色.用Ci-1∪｛a2｝中的m＋1種顏色對Hi進(jìn)行正常全染色，使得Hi的所有頂點均不染顏色a2，其中i＝1，2，…，n-1.

顯然，在H0的全染色中，顏色a1在X的每一頂點上不表現(xiàn)，顏色a0在Y的每一頂點上不表現(xiàn).

其次，對G（2）進(jìn)行正常邊染色.取G01的一個完美匹配 M＝｛v0kv1k｜k＝1，2，…，m｝.若v0k∈X，則用顏色a1染色v0kv1k；若v0k∈Y，則用顏色a0染邊v0kv1k.并用C1-｛c1，0｝中的m-1種顏色對（m-1）-正則二部圖G01-M進(jìn)行正常邊染色.用Ci（下標(biāo)取模n-1）中m種顏色對m-正則二部圖G0i進(jìn)行正常邊染色，i＝2，3，…，n-1.

最后，對G（3）進(jìn)行正常邊染色，染色方法與定理1證明中的相同.

容易看出，以上染色為G［hn］的一個（Δ0＋（n-1）m＋1）-正常全染色，故有χT（G［hn］）≤Δ0＋（n-1）m＋1.因此，χT（G［hn］）＝Δ0＋（n-1）m＋1，即定理結(jié)論成立.

定理4 設(shè)G 為n 階輪，或扇，或星，其中n≥5.在hn＝（Hi）i∈｛0，1，…，n-1｝中，｜Hi｜＝m 對于i＝0，1，…，n-1.若H0為m 階圈，m≥3，則χT（G［hn］）＝（n-1）m＋3.

證明 當(dāng)m 為偶數(shù)時，H0為二部圈，所以H0為二部圖.由定理3，χT（G［hn］）＝（n-1）m＋3.

當(dāng)m 為奇數(shù)時，顯然，χT（G［hn］）≥Δ（G［hn］）＋1＝（n-1）m＋3.與定理1的證明類似，我們僅需證明，當(dāng)G＝Wn時，χT（G［hn］）≤（n-1）m＋3.

首先，對G（1）進(jìn)行正常全染色.由引理1與引理2，用Ci-1中的m種顏色對Hi進(jìn)行正常全染色，其中i＝1，2，…，n-1.因 H0為奇圈，所以可用Cn-1∪｛c1，0｝中的4種顏色對 H0進(jìn)行正常全染色，具體地，令

顯然，在 H0的全染色中，顏色c1，0不在頂點v0，1，v0，m-1與v0，m上表現(xiàn)，而在頂點v0，2，v0，3，…，v0，m-2上交替地缺少顏色a0與a1.

其次，對G（2）進(jìn)行正常邊染色.取G01的一個完美匹配M＝｛v0kv1k｜k＝1，2，…，m｝，用頂點v0k上未表現(xiàn)的顏色染邊v0kv1k.并用C1-｛c1，0｝中的m-1種顏色對（m-1）-正則二部圖G01-M 進(jìn)行正常邊染色.用Ci（下標(biāo)取模n-1）中m種顏色對m-正則二部圖G0i進(jìn)行正常邊染色，i＝2，3，…，n-1.

最后，對G（3）進(jìn)行正常邊染色，染色方法與定理1證明中的相同.

容易看出，以上染色為G［hn］的一個（（n-1）m＋3）-正常全染色，所以有χT（G［hn］）≤（n-1）m＋3.因此，χT（G［hn］）＝（n-1）m＋3，即定理成立.

［1］Bondy J A，Murty U S R.Graph Theory with Application［M］.New York：American Elsevier，1976.

［2］Waldemar Szumny，Iwona W?yoch，Andrzej W?och.On the Existence and on the Number of（k，l）-kernels in the Lexicographic Product of Graphs［J］.Discrete Mathematics，2008，308：4616-4624.

［3］Tian Shuang-liang.Star Total Colorings of Mycielski’s Graphs of Balanced General Join of Graph［J］.Journal of Shandong University：Natural Science，2009，45（6）：23-26，34.

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

［5］Behzad.Graphs and Their Chromatic Numbers［M］.Doctoral Thesis，Michigan State University，1965.

［6］Kostochka A V.The Total Coloring of Multigraph with Maximal Degree 4［J］.Discrete Mathematics，1977，17：161-163.

［7］Seoung M A.Total Chromatic Numbers［J］.Appl Math Lett，1992，5：37-39.

［8］Yap H P.Total Coloring of Graph［M］.New York：Springer Verlag，1996.