關(guān)于雙圈圖的動(dòng)態(tài)色數(shù)

尚華輝，閆曉芳，苗連英

(1.中國(guó)礦業(yè)大學(xué) 數(shù)學(xué)系，江蘇 徐州 221008；2.永城職業(yè)學(xué)院 基礎(chǔ)部，河南 永城 476600)

本文研究的是有限、無(wú)向且連通的簡(jiǎn)單圖。給定圖G，分別用V(G)、E(G)表示G的頂點(diǎn)集、邊集。對(duì)圖G中任意頂點(diǎn)v，分別用d(v)、N(v)表示v的度數(shù)、鄰點(diǎn)的集合。用Cn表示包含n個(gè)頂點(diǎn)的圈，其余概念參見(jiàn)文獻(xiàn)[1].

圖G的色數(shù)χ(G)是指對(duì)圖G的頂點(diǎn)進(jìn)行染色，使得任意2個(gè)相鄰的頂點(diǎn)染不同顏色所需要的最少顏色數(shù)。G的動(dòng)態(tài)染色是從頂點(diǎn)集到顏色集的一個(gè)映射，且滿足下列2個(gè)條件：

1) 如果uv∈E(G)，則c(u)≠c(v)；

2) 對(duì)任意的頂點(diǎn)v∈V(G)，|c(N(v))|≥min{2,d(v)}.如果用k種顏色可以得到圖G的一個(gè)動(dòng)態(tài)染色，則稱G有一個(gè)動(dòng)態(tài)k-染色(或稱G是動(dòng)態(tài)k-可染的)。動(dòng)態(tài)色數(shù)χd(G)是使得G有一個(gè)動(dòng)態(tài)k-染色的最小的k.

動(dòng)態(tài)染色是在文獻(xiàn)[2]中提出來(lái)的。在文獻(xiàn)[3]中進(jìn)行了更深入地研究，證明了χd(G)≤Δ+3，并給出了樹(shù)、圈、二分圖、完全二分圖,以及完全多部圖的動(dòng)態(tài)色數(shù)。文獻(xiàn)[4]給出了Halin圖和Series-Parallel圖的動(dòng)態(tài)色數(shù)，文獻(xiàn)[5]給出了單圈圖和大部分雙圈圖的動(dòng)態(tài)色數(shù)。設(shè)T是p(p≥3)階樹(shù)，將T中某2個(gè)不相鄰的點(diǎn)用一條新的邊連接起來(lái)，得到的p階含有p條邊的圖稱為單圈圖?；蛘哒f(shuō)，恰含有1個(gè)圈的連通圖稱為單圈圖。雙圈圖是指邊數(shù)比頂點(diǎn)數(shù)多1的簡(jiǎn)單連通圖。文獻(xiàn)[5]沒(méi)有給出當(dāng)兩個(gè)雙圈有公共路時(shí)且公共路上有懸掛分支的這一較復(fù)雜情況。本文通過(guò)構(gòu)造3個(gè)子圖，解決了這種情況下的雙圈圖的動(dòng)態(tài)色數(shù)，從而徹底解決了雙圈圖的動(dòng)態(tài)色數(shù)問(wèn)題。

1 主要引理

引理1[2]設(shè)G是一個(gè)連通的非平凡圖，則χd(K2)=2.除此之外χd(K2)≥3.

引理2[2]除了K1和K2，任何樹(shù)G的χd(G)=3.

設(shè)雙圈圖G上的兩個(gè)圈分別為C1和C2.按照圈C1和C2相交的情況，將雙圈圖分為相交雙圈圖、無(wú)交雙圈圖和有公共路的雙圈圖。

在G中，構(gòu)造了兩個(gè)子圖H1，H2，通過(guò)研究H1，H2的動(dòng)態(tài)色數(shù)來(lái)刻畫(huà)G的動(dòng)態(tài)色數(shù)，見(jiàn)參考文獻(xiàn)[5].

引理4[5]設(shè)G是用上述方法構(gòu)造的雙圈圖G的子圖，則

χd(G)=max{χd(H1),χd(H2)} .

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

在給出主要結(jié)果之前,先做一些說(shuō)明。

設(shè)G為雙圈圖，與G中的兩圈相關(guān)聯(lián)的連通分支(包含圈上的相應(yīng)點(diǎn)，該點(diǎn)稱為附著頂點(diǎn))稱為雙圈圖G的懸掛分支。顯然雙圈圖的任何懸掛分支都是樹(shù)。

除非特別說(shuō)明，下文中的路均是指始點(diǎn)和終點(diǎn)在圖G中的度均大于2，路上中間各點(diǎn)的度均為2.比如路(ui,uj)表示一條uiu1u2…umuj路，則路(ui,uj)的長(zhǎng)度為m+1，且d(ui)>2，d(uj)>2，d(ut)=2，(t=1,2,…,m).若設(shè)c(ui)=1，c(u1)=2，則用1,2,3等3種顏色給(ui,uj)染色時(shí)，u2,u3,…,um,uj染的顏色順序必是3,1,2,3,1,2,3,….即給定其中一端相鄰兩點(diǎn)確定的顏色后，其它點(diǎn)的顏色是被唯一確定的。根據(jù)以上染色過(guò)程，可以得出如下結(jié)論。

結(jié)論1 若(ui,uj)的長(zhǎng)為3s+1(s=0,1,2,…)或3t+2(t=0,1,2,…)，且存在染色使得點(diǎn)ui,u1,u2,…,um,uj都滿足動(dòng)態(tài)染色的要求，則c(ui)≠c(uj).

結(jié)論2 若2條長(zhǎng)為3s+1(s=0,1,2,…)或3t+2(t=0,1,2,…)的路首尾相鄰于某頂點(diǎn)v，并把頂點(diǎn)v上原有的懸掛分支加上，形成的圖(G的子圖)的始點(diǎn)和終點(diǎn)的顏色可以相同也可以不同。

比如(ui,uj)的長(zhǎng)為3s+1(s=0,1,2,…)或者3t+2(t=0,1,2,…)，路(uj,uk)的長(zhǎng)為3s+1(s=0,1,2,…)或者3t+2(t=0,1,2,…)，注意到兩路的連接點(diǎn)uj上一定存在懸掛分支，通過(guò)適當(dāng)調(diào)整懸掛分支的染色可以使c(ui)≠c(uk)或c(ui)=c(uk).

結(jié)論3 若(ui,uj)的長(zhǎng)為3s(s=0,1,2,…)，且存在1個(gè)染色使得此路上的ui,u1,u2,…,um,uj點(diǎn)都滿足動(dòng)態(tài)染色的要求，則必有c(ui)=c(uj).

結(jié)論4 若2條以上(包含2條)為3s(s=0,1,2,…)的路首尾相鄰于某頂點(diǎn)v，并把頂點(diǎn)v上原有的懸掛分支加上，形成的圖(G的子圖)的始點(diǎn)和終點(diǎn)的顏色還相同。

比如(ui,uj)的長(zhǎng)為3s(s=0,1,2,…)，路(uj,uk)的長(zhǎng)為3t(t=0,1,2,…).無(wú)論怎樣調(diào)整懸掛分支的染色，必有c(ui)=c(uk).

下面研究當(dāng)2個(gè)雙圈有公共路時(shí)且公共路上有懸掛分支的雙圈圖的動(dòng)態(tài)色數(shù)。

設(shè)公共路Pm上的點(diǎn)依次為v1,v2,…,vm-1,vm,C1,C2表示圖G中的2個(gè)圈。為了證明的需要，標(biāo)記如下子圖：C'1=C1-{v2,v3,…,vm-1},C'2=C2-{v2,v3,…,vm-1}，用r表示路C'1=C1-{v2,v3,…,vm-1}上被附著的懸掛分支分成的路長(zhǎng)為3s+1(s=0,1,2,…)或者3t+2(t=0,1,2,…)的路的個(gè)數(shù)，用t表示路C'2=C2-{v2,v3,…,vm-1}上被附著的懸掛分支分成的路長(zhǎng)為3s+1(s=0,1,2,…)或者3t+2(t=0,1,2,…)路的個(gè)數(shù)，用p表示路Pm上被附著的懸掛分支分成的路長(zhǎng)為3s+1(s=0,1,2,…)或者3t+2(t=0,1,2,…)路的個(gè)數(shù)。不妨設(shè)r≥t，在上面的構(gòu)造和分析的基礎(chǔ)上,將證明本文的主要結(jié)論。

定理1 若圖G是雙圈圖，雙圈C1，C2有公共路Pm且公共路上有懸掛分支，則有

否則χd(G)=4.

證明：設(shè)圖C'表示路C'1,C'2及其路C'1,C'2上所有附著的懸掛分支構(gòu)成的圖。不失一般性，記Pm中v1的顏色為c(v1)=1.根據(jù)路C'1,C'2的對(duì)稱性，只需證r≥t時(shí)的情況。

情況1 當(dāng)r=t=0時(shí)，由結(jié)論3可知，用3種顏色1，2，3可以滿足圖G'的動(dòng)態(tài)染色的要求且有c(v1)=c(vm)；又由引理1可知χd(G')≥3.基于此，考察G是否是動(dòng)態(tài)3-可染的，現(xiàn)只需考察3種顏色1，2，3在滿足G'動(dòng)態(tài)可染的基礎(chǔ)上考察路Pm上點(diǎn)v2,v3,…,vm-1的染色。

1) 當(dāng)p=0或者p≥2時(shí)，用顏色1,2,3滿足G'且滿足Pm上v1,v2,…,vm-1,vm各頂點(diǎn)的動(dòng)態(tài)染色的要求，且滿足c(v1)=c(vm).故χd(G)=3.

2) 當(dāng)p=1時(shí)，由結(jié)論1知用顏色1,2,3同時(shí)滿足Pm上v1,v2,…,vm-1,vm必有c(v1)≠c(vm)，與為了滿足G'而必有c(v1)=c(vm)矛盾，故χd(G)≥4.易驗(yàn)證用4種顏色染能滿足要求，故動(dòng)態(tài)色數(shù)χd(G)=4.

情況2 當(dāng)s=1且t=0時(shí)，在圖G'中，用顏色1,2,3為滿足C'1=C1-{v2,v3,…,vm-1}的動(dòng)態(tài)染色需要c(v1)≠c(vm)，而為滿足C'2=C2-{v2,v3,…,vm-1}需要c(v1)=c(vm)，故χd(G')≥4.易驗(yàn)證不論p的取值如何，用4種顏色能滿足圖G動(dòng)態(tài)染色的要求。故動(dòng)態(tài)色數(shù)χd(G)=4.

由結(jié)論3知，G'中的長(zhǎng)為形如3s(s=1,2,…)的路對(duì)G'及其G的色數(shù)無(wú)影響，故下面的證明過(guò)程中，不妨設(shè)G'中不存在這樣的路。

情況3 當(dāng)s=t=1時(shí)，此情況下C'1=C1-{v2,v3,…,vm-1},C'2=C2-{v2,v3,…,vm-1}是2條路，且路中間的頂點(diǎn)上無(wú)附著懸掛分支。不妨記2條路分別為P1,P2.下面根據(jù)路P1與P2的階數(shù)差的絕對(duì)值‖V(P1)|-|V(P2)‖來(lái)討論：

1) 當(dāng)‖V(P1)|-|V(P2)‖=0(mod3)時(shí)，這種情況下v1，vm上是否附著懸掛分支對(duì)整個(gè)圖的色數(shù)時(shí)有影響的，故根據(jù)v1,vm上懸掛分支的數(shù)量來(lái)討論當(dāng)2頂點(diǎn)v1,vm中至少存在一頂點(diǎn)上附著有懸掛分支，則易驗(yàn)證適當(dāng)調(diào)整分支的顏色，滿足G'是動(dòng)態(tài)-3可染的，結(jié)合引理1知χd(G')=3，且有c(v1)≠c(vm).接下來(lái)根據(jù)Pm上p的大小討論G的動(dòng)態(tài)色數(shù)。

a.當(dāng)p≥1時(shí)，在圖G'中，用顏色1,2,3給G'染色時(shí)，v1或vm在C'1=C1-{v2,v3,…,vm-1}和C'2=C2-{v2,v3,…,vm-1}中的鄰點(diǎn)所染的顏色可能相同，但適當(dāng)調(diào)整v1,vm上懸掛分支的顏色分支來(lái)調(diào)整v1或者vm在圖G中的鄰點(diǎn)集的色數(shù)(當(dāng)p≥2時(shí)，也可以調(diào)整v2,v3,…,vm-1上的分支色數(shù)來(lái)配合G整個(gè)的動(dòng)態(tài)色數(shù))使Pm上的v2,v3,…,vm-1也滿足動(dòng)態(tài)3-染色的要求，故χd(G)=3.

b.當(dāng)p=0時(shí)，用顏色1,2,3給Pm染色時(shí)，必有c(v1)=c(vm)，與用顏色1,2,3能滿足G'動(dòng)態(tài)3-染色矛盾(因?yàn)橛妙伾?,2,3給G'動(dòng)態(tài)染色時(shí)必有c(v1)≠c(vm))，與是否有懸掛分支無(wú)關(guān)，故χd(G)≥4.易驗(yàn)證4種顏色能滿足G的動(dòng)態(tài)染色的要求，故χd(G)=4.

2) 當(dāng)‖V(P1)|-|V(P2)‖≠0(mod3)時(shí)，注意到此時(shí)的G'除去其上的所有懸掛分支就是一個(gè)長(zhǎng)度為3s(s=2,3,…)的圈。故由引理3知用顏色1,2,3可滿足其動(dòng)態(tài)染色的要求，由結(jié)論4知：G'也滿足是動(dòng)態(tài)3-可染的，且必有c(v1)≠c(vm).故考察G是否是動(dòng)態(tài)3-染色的，只需考察路Pm上的染色。

a. 若p≥1，由引理1知，3種顏色能滿足Pm是動(dòng)態(tài)3-染色的，故χd(G)=3.

b.p=0，不論v1,vm上是否有懸掛分支對(duì)路Pm的動(dòng)態(tài)色數(shù)沒(méi)有本質(zhì)的影響，即動(dòng)態(tài)染Pm需要4種不同的顏色，故χd(G)≥4，易驗(yàn)證用4種顏色滿足圖G其動(dòng)態(tài)染色要求，即有χd(G)=4.

情況4 若C'1=C1-{v2,v3,…,vm-1}中的m≥2,C'2=C2-{v2,v3,…,vm-1}中的n≥1,其中(m≥n).同上述情況2)類似討論可得：

若p≥1,則χd(G)=3；若p=0,則χd(G)=4.

至此，完成了定理1的證明。

文獻(xiàn)[5]給出了一個(gè)不能用引理4判定其動(dòng)態(tài)色數(shù)的例子，但易見(jiàn)可用定理1得出其動(dòng)態(tài)色數(shù)。上述定理包含引理4的的第一和第三種情況：不難看出相交雙圈圖可以看成是有公共路雙圈圖當(dāng)公共路Pm上的p=0時(shí)的特殊情況；從上述證明過(guò)程可得：可把有公共路且沒(méi)有懸掛分支的雙圈圖的情形看成公共路僅被懸掛分支分成一部分即可。