關于雙圈圖的動態色數

尚華輝，閆曉芳，苗連英

(1.中國礦業大學 數學系，江蘇 徐州 221008；2.永城職業學院 基礎部，河南 永城 476600)

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

圖G的色數χ(G)是指對圖G的頂點進行染色，使得任意2個相鄰的頂點染不同顏色所需要的最少顏色數。G的動態染色是從頂點集到顏色集的一個映射，且滿足下列2個條件：

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

2) 對任意的頂點v∈V(G)，|c(N(v))|≥min{2,d(v)}.如果用k種顏色可以得到圖G的一個動態染色，則稱G有一個動態k-染色(或稱G是動態k-可染的)。動態色數χd(G)是使得G有一個動態k-染色的最小的k.

動態染色是在文獻[2]中提出來的。在文獻[3]中進行了更深入地研究，證明了χd(G)≤Δ+3，并給出了樹、圈、二分圖、完全二分圖,以及完全多部圖的動態色數。文獻[4]給出了Halin圖和Series-Parallel圖的動態色數，文獻[5]給出了單圈圖和大部分雙圈圖的動態色數。設T是p(p≥3)階樹，將T中某2個不相鄰的點用一條新的邊連接起來，得到的p階含有p條邊的圖稱為單圈圖。或者說，恰含有1個圈的連通圖稱為單圈圖。雙圈圖是指邊數比頂點數多1的簡單連通圖。文獻[5]沒有給出當兩個雙圈有公共路時且公共路上有懸掛分支的這一較復雜情況。本文通過構造3個子圖，解決了這種情況下的雙圈圖的動態色數，從而徹底解決了雙圈圖的動態色數問題。

1 主要引理

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

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

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

在G中，構造了兩個子圖H1，H2，通過研究H1，H2的動態色數來刻畫G的動態色數，見參考文獻[5].

引理4[5]設G是用上述方法構造的雙圈圖G的子圖，則

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

2 主要結果及其證明

在給出主要結果之前,先做一些說明。

設G為雙圈圖，與G中的兩圈相關聯的連通分支(包含圈上的相應點，該點稱為附著頂點)稱為雙圈圖G的懸掛分支。顯然雙圈圖的任何懸掛分支都是樹。

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

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

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

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

結論3 若(ui,uj)的長為3s(s=0,1,2,…)，且存在1個染色使得此路上的ui,u1,u2,…,um,uj點都滿足動態染色的要求，則必有c(ui)=c(uj).

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

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

下面研究當2個雙圈有公共路時且公共路上有懸掛分支的雙圈圖的動態色數。

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

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

否則χd(G)=4.

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

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

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

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

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

由結論3知，G'中的長為形如3s(s=1,2,…)的路對G'及其G的色數無影響，故下面的證明過程中，不妨設G'中不存在這樣的路。

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

1) 當‖V(P1)|-|V(P2)‖=0(mod3)時，這種情況下v1，vm上是否附著懸掛分支對整個圖的色數時有影響的，故根據v1,vm上懸掛分支的數量來討論當2頂點v1,vm中至少存在一頂點上附著有懸掛分支，則易驗證適當調整分支的顏色，滿足G'是動態-3可染的，結合引理1知χd(G')=3，且有c(v1)≠c(vm).接下來根據Pm上p的大小討論G的動態色數。

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

b.當p=0時，用顏色1,2,3給Pm染色時，必有c(v1)=c(vm)，與用顏色1,2,3能滿足G'動態3-染色矛盾(因為用顏色1,2,3給G'動態染色時必有c(v1)≠c(vm))，與是否有懸掛分支無關，故χd(G)≥4.易驗證4種顏色能滿足G的動態染色的要求，故χd(G)=4.

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

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

b.p=0，不論v1,vm上是否有懸掛分支對路Pm的動態色數沒有本質的影響，即動態染Pm需要4種不同的顏色，故χd(G)≥4，易驗證用4種顏色滿足圖G其動態染色要求，即有χ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的證明。

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