特殊點(diǎn)分裂圖的Grundy著色問題

楊晨旭，姚慶燁，鄧興超

（天津師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院，天津300387）

1 引言和預(yù)備知識

近些年，圖的著色理論隨著計算機(jī)理論的發(fā)展得到進(jìn)一步完善，基于實際和理論需要，各種類型的著色問題被提出[1-3].Grundy著色最早由Christen等[4]基于貪婪算法提出，并討論了完美圖的Grundy著色.文獻(xiàn)[5]討論了Grundy著色算法的復(fù)雜性問題.文獻(xiàn)[6]討論了Grundy著色的Nordhaus-Gaddum-type不等式.有關(guān)Grundy著色的最新進(jìn)展可參見文獻(xiàn)[7-8].本文考慮路、圈、輪和扇的點(diǎn)分裂圖的Grundy著色問題，通過構(gòu)造出具體的著色方案，利用反證法得到這4類特殊點(diǎn)分裂圖的Grundy色數(shù).

本文研究的圖是有限、無向的簡單圖（無重邊且無自環(huán)）.頂點(diǎn)集合為V、邊集合為E的圖記為G=（V，E）.υ（G）表示圖G的階，即υ（G）=|V（G）|.在不引起歧義的情況下，圖G的邊數(shù)用e（G）表示，即e（G）=|E（G）|.對于v∈V（G），用NG（v）表示頂點(diǎn)v的鄰域，v的度記為d（v），即d（v）=|NG（v）|，圖G的最小度和最大度分別記為δ（G）和Δ（G）.對于S?V（G），由頂點(diǎn)集S導(dǎo)出的子圖記為G[S]，并將G[VS]記為GS或G-S，特別地，記G[V{v}]=G-v，G的補(bǔ)圖記為G.對于2個正整數(shù)m

定義1[9]圖G（V，E）的k正常著色是指一個映射φ：V→[1，k]，滿足：對于任意邊uv∈E（G），φ（u）≠φ（v）.若圖G存在一個正常的k著色，則稱圖G是k可著色的，稱χ（G）=min{k|圖G存在一個正常的k著色}為圖G的色數(shù).

定義2[6]（Grundy著色）設(shè)k>0且k∈N，圖G（V，E）的Grundy著色是指一個映射φ：V→[1，k]，滿足以下條件：

（1）對于任意邊uv∈E（G），φ（u）≠φ（v）.

（2）對于滿足1≤m

引理1[10]對于任意圖G，有χ（G）≤Γ（G）.

引理2[10]對于任意圖G，有Γ（G）≤Δ（G）+1.

定義3[9]設(shè)G和H為2個點(diǎn)不交的圖，G和H的聯(lián)圖G∨H定義為

定義4[11]設(shè)G為簡單圖，其頂點(diǎn)集為V（G）={v1，v2，…，vn}，設(shè)I2為含有2個點(diǎn)的獨(dú)立集.用I2替換G的每個頂點(diǎn)得到的圖記為G[I2].I2中的每個點(diǎn)仍按對應(yīng)點(diǎn)的連邊方式與其他點(diǎn)相連.G[I2]的點(diǎn)集和邊集分別為

稱G[I2]為G的點(diǎn)分裂圖.

例如：一條邊K2的點(diǎn)分裂圖為K2[I2]?C4.

2 主要結(jié)果

定理1路Pn的點(diǎn)分裂圖Pn[I2]的Grundy色數(shù)Γ（Pn[I2]）為

證明（1）當(dāng)n=2時，P2[I2]?C4，設(shè)φ（v1）=1，φ（v3）=1，φ（v2）=2，φ（v4）=2，則φ為P2[I2]的一個Grundy 2著色函數(shù).由引理2可知Γ（P2[I2]）≠3，所以Γ（P2[I2]）=2.

（2）當(dāng)n=3時，設(shè)φ（v1）=1，φ（v2）=2，φ（v3）=1，φ（v1′）=1，φ（v2′）=2，φ（v3′）=1，則φ為P3[I2]的一個Grundy 2著色函數(shù).下面證明Γ（P3[I2]）<3，由Grundy著色的定義可知，頂點(diǎn)v1至多可著3種顏色，不妨設(shè)φ（v1）∈{1，2，3}.

情況1當(dāng)φ（v1）=1時，由引理2可知，φ（v2）∈{2，3，4，5}，φ（v2′）∈{2，3，4，5}.如果φ（v3）=3，則有φ（NG（v3））={φ（v2），φ（v2′）}={1，2}，但v1∈{NG（v2）}且φ（v1）=1，與定義矛盾.因此φ（v3）=2或φ（v3′）=2，則由定義可得1∈φ（NG（v3）），即φ（v2′）=1或φ（v2）=2.若1∈φ（NG（v3′）），即φ（v2′）=1或φ（v2）=1，但v1與v2和v2′相鄰，矛盾.

情況2當(dāng)φ（v1）=2時，有φ（NG（v1））={1}，因為NG（v1）=NG（v3）=NG（v3′）={v2，v2′}，則φ（v2）=1，φ（v2′）=1，從而Γ（P3[I2]）<3.

情況3當(dāng)φ（v1）=3時，有φ（NG（v1））={1，2}，NG（v1）=NG（v3）=NG（v3′）={v2，v2′}，因此φ（v2）=1，φ（v2′）=2或φ（v2）=2，φ（v2′）=1，若φ（v2）=1，φ（v2′）=2，則要保證φ（NG（v2′））={1}，因為NG（v2′）={v1，v3，v3′}，但是NG（v2′）=NG（v2），所以這是不可能的.若φ（v2）=2，φ（v2′）=1，則要保證φ（NG（v2））={1}，但是NG（v2′）=NG（v2）={v1，v3，v1′，v3′}，顯然v1不能著顏色1，因此Γ（P3[I2]）<3.

綜上可得Γ（P3[I2]）=2.

由著色函數(shù)可知φ（v1）=1，φ（v1′）=1；當(dāng)i>3且為偶數(shù)時，φ（vi）=1，φ（v2）=2，φ（v2′）=2；當(dāng)i>3且為奇數(shù)時，φ（vi）=2.故當(dāng)i>3且為奇數(shù)時，上述著色函數(shù)滿足1∈φ（NG（v2））且1∈φ（NG（vi）），又因為φ（v3）=3，φ（v3′）=3，NG（v3′）={v2，v2′，v4，v4′}，φ（v4）=1，φ（v4′）=1，φ（v2）=2，φ（v2′）=2，因此有{1，2}?φ（NG（v3）），{1，2}?φ（NG（v3′）），所 以φ是 一 個 真Grundy 3著色.當(dāng)i>3且為偶數(shù)時，同理可得φ是一個真Grundy 3著色.

由引理2可知Γ（Pn[I2]）∈{3，4，5}，要證明Γ（Pn[I2]）=3，只需證明Γ（Pn[I2]）?{4，5}.

首先證明Γ（Pn[I2]）≠5.若Γ（Pn[I2]）=5，則存在某個頂點(diǎn)v，滿足φ（v）=5且v是度最大的頂點(diǎn)，即d（v）=4，否則其鄰點(diǎn)集著色不滿足定義要求.

用{v-2，v-1，v，v1，v2}和{v-2′，v-1′，v′，v1′，v2′}表示v的鄰點(diǎn)集合，其中v-2為v左邊的第2個頂點(diǎn).如果頂點(diǎn)v∈V（G），φ（v）=5，則要保證φ（NG（v））={1，2，3，4}，因為d（v）=4，故有φ（v-1′）≠φ（v1′）≠φ（v1）≠φ（v-1）.

假設(shè)φ（v-1）=3，由于d（v-1）=4，NG（v-1）={v-2，v，v-2′，v′}，φ（v）=5，則要保證φ（NG（v-1））={1，2，3}，又d（v-1）=4，所以φ（v-2′）≠φ（v2′）≠φ（v）≠φ（v′）.不妨設(shè)φ（v′）=j，1≤j≤3，因為NG（v）=NG（v′），若v′著顏色j，而Grundy著色是正常著色，因此v′的鄰點(diǎn)不能著顏色j，也就是v的鄰點(diǎn)缺少顏色j，顯然這種著色方法不滿足定義，因此Γ（Pn[I2]）≠5.

然后證明Γ（Pn[I2]）≠4.若Γ（Pn[I2]）=4，則存在頂點(diǎn)v，滿足φ（v）=4，則要保證φ（NG（v））={1，2，3}，因為d（v）=4，不妨設(shè)φ（v-1）=3，NG（v-1）={v-2，v，v-2′，v′}，故有{1，2}?{φ（v-2′），φ（v2′），φ（v′）}，顯然這種著色方法不滿足定義.當(dāng)φ（v′）=4時，有{1，2}={φ（v-2′），φ（v2′）}.由于φ（NG（v-2））=φ（NG（v-2′）），若φ（v-2′）=1，則1?φ（NG（v-2）），若φ（v-2′）=2，則1?φ（NG（v-2′）），也不滿足定義.因此Γ（Pn[I2]）≠4.

經(jīng)濟(jì)的發(fā)展和生態(tài)環(huán)境的惡化使人們對森林資源的重視程度不斷的提升，許多地區(qū)都在進(jìn)行林業(yè)工程的建設(shè)，這使我國的森林資源走勢發(fā)生變化，同時森林資源不斷增加。然而在一些地區(qū)的林業(yè)工程建設(shè)中存在一定的問題，即營造林的質(zhì)量不高。出現(xiàn)這種情況的因素有多種，尤其重要的是營造林質(zhì)量不高。

綜上可得Γ（Pn[I2]）=3.

定理2圈Cn的點(diǎn)分裂圖Cn[I2]的Grundy色數(shù)Γ（Cn[I2]）為

證明（1）當(dāng)n=4時，在圈上交替著顏色1和2即可，故Γ（C4[I2]）=2.

（2）當(dāng)n≠4時，首先給出Cn[I2]的一個Grundy 3著色函數(shù).當(dāng)n為奇數(shù)時，

當(dāng)n為偶數(shù)時，

利用與定理1類似的方法可證明φ是一個真Grundy

3 著色.

由引理2可知Γ（Cn[I2]）∈{3，4，5}，與路的點(diǎn)分裂圖類似，可證明Γ（Cn[I2]）≠4且Γ（Cn[I2]）≠5，故Γ（Cn[I2]）=3.

定理3扇Fn的點(diǎn)分裂圖Fn[I2]的Grundy色數(shù)Γ（Fn[I2]）為

證明（1）當(dāng)n=2時，F(xiàn)2=C3，由定理2可得Γ（C3[I2]）=Γ（F2[I2]）=3.

（2）當(dāng)n=3時，在輪上交替著顏色1和2，輪心著顏色3即可，故Γ（F3[I2]）=3.

（3）當(dāng)n≥4時，首先給出Fn[I2]的一個真Grundy 4著色函數(shù)

下面證明Γ（Fn[I2]）<5.在Fn[I2]上，每個輪圈上頂點(diǎn)的度均為6，因此Γ（Fn[I2]）≤7，否則與Grundy著色定義矛盾.

首先證明Γ（Fn[I2]）<7.

情況1設(shè)在輪圈上存在一個頂點(diǎn)v，φ（v）=7，此時v-1′、v1′、v0′、v0、v-1、v1著顏色1，2，…，6，且各不相同，不妨設(shè)φ（v-1）=6，由于NG（v）=NG（v′），所以v′不能著顏色1、2、3、4、5，否則φ（NG（v））≠{1，2，3，4，5，6}.因此φ（v′）=7.又因為φ（v-1）=6，則φ（NG（v-1））={1，2，3，4，5}，即v-2、v-2、v0′、v0′要用完1、2、3、4、5這5種顏色，這顯然不可能.故φ（v-1）≠6，矛盾.

情況2若φ（v0）=φ（v0′）=7，則只需證明在輪圈上不存在頂點(diǎn)v，滿足φ（v）=6.若頂點(diǎn)v在輪圈上，且φ（v）=6，頂點(diǎn)v和v0、v0′都相鄰，因此v-2、v-1、v0′、v0′需著顏色1、2、3、4、5，且各不相同，這顯然是矛盾的.

下面證明Γ（Fn[I2]）<6.

情況1設(shè)在輪圈上存在一個頂點(diǎn)v，φ（v）=6，顯然φ（v0）=φ（v0′），若φ（v0′）=φ（v0）=5，則有φ（v-1）≠φ（v1）≠φ（v-1′）≠φ（v1′）∈{1，2，3，4}，不妨設(shè)φ（v-1）=4，則φ（v′）、φ（v-2′）、φ（v-2）中必有一個等于3.若φ（v′）=3，由NG（v）=NG（v′）可知3?φ（NG（v）），矛盾；若φ（v-2′）=3，則有{φ（v-3），φ（v-3′）}={1，3}，矛盾；同理，若φ（v-2）=3，也會導(dǎo)致矛盾.

情況2若φ（v0）=φ（v0′）=6，則只需證明在輪圈上不存在頂點(diǎn)v，滿足φ（v）=5.若頂點(diǎn)v在輪圈上，且φ（v）=5，頂點(diǎn)v和v0、v0′都相鄰，此時v-1′、v1′、v-1、v1著顏色1、2、3、4，并且各不相同，類似于情況1的證明過程可知這是矛盾的.

類似于Γ（Fn[I2]）<7和Γ（Fn[I2]）<6的證明，可以得到Γ（Fn[I2]）<5.綜上可得Γ（Fn[I2]）=4.

定理4輪Wn的點(diǎn)分裂圖Wn[I2]的Grundy色數(shù)Γ（Wn[I2]）為

證明（1）當(dāng)n=4時，令

容易證明φ是一個真Grundy3著色.又因為Γ（W4[I2]）≤3，故Γ（W4[I2]）=3.

（2）當(dāng)n≠4時，首先給出Wn[I2]的一個真Grundy 4著色函數(shù).當(dāng)n為奇數(shù)時，

當(dāng)n為偶數(shù)時,

由Γ（Wn[I2]）≤5，只需證明Γ（Wn[I2]）≠5.設(shè)輪的中心為v0、v0′，并設(shè){…，u-2，u-1，u1，u2，…}為某個輪的頂點(diǎn)集合.若Γ（Wn[I2]）=5，則著顏色5的頂點(diǎn)位于輪上或中心，利用與定理3類似的證明過程可知這2種情況都是不可能的，因此Γ（Wn[I2]）=4.