若干倍圖的均勻染色*

傅彩霞

(浙江師范大學數理與信息工程學院，浙江金華 321004)

0 引言

本文所考慮的圖是簡單無向圖．對于圖G，用V(G)，E(G)，|V(G)|和Δ(G)分別表示G的頂點集、邊集、階和最大度．圖G的正常k-染色是指映射f:V(G)→{1，2，…，k}滿足?uv∈E(G)，f(u)≠f(v)．用χ(G)表示G是正常k-可染的最小整數k．在圖的染色中，均勻染色是一個重要的染色問題．

定義1 對|V(G)|≥2 的簡單圖 G(V，E)的正常 k-染色 f，若滿足?i，j∈{1，2，…，k}，||Vi|-|Vj||≤1，則稱f為G的一個k-均勻染色．χe(G)表示G是k-均勻可染的最小整數k，稱為G的均勻色數．其中Vi={v|v∈V(G)，f(v)=i}，i=1，2，…，k．

1964年，Erd?s［1］給出猜想:任何一個圖 G 和整數 k≥Δ(G)，G 是(k+1)-均勻可染的．這一猜想于1970 年被 Hajnal和 Szemerédi［2］所證明，即對于圖 G，當 k≥Δ(G)+1 時，G 是 k-均勻可染的．在此基礎上，Meyer［3］于1973年提出了如下猜想:若連通圖G 不為完全圖和奇圈，則 χe(G)≤Δ(G)．1994年，Chen等［4］進一步提出了如下猜想:不為Km，C2m+1和K2m+1，2m+1(m≥1)的連通圖G 是 Δ(G)-均勻可染的．他們在同一文獻中運用換色法等技巧給出了下面3個結論:1)對于Δ(G)≤3的連通圖G，G是Δ(G)-均勻3)不為Kn，n的連通二部圖G是Δ(G)-均勻可染的．文獻［5］證明了Chen等的猜想對外平面圖成立，同勻可染的．文獻［7］給出了一個漂亮的結果:對于平面圖G，若Δ(G)≥13，則G是Δ(G)-均勻可染的．本文討論了星、扇、輪和棱柱Lm的倍圖的均勻染色問題．

定義2［8］對簡單圖G，G'是G 的拷貝，若V(D(G))=V(G)∪V(G')，E(D(G))=E(G)∪ E(G')∪{uivj|ui∈V(G)，vj∈V(G')且 uiuj∈E(G)}，則稱 D(G)為 G 的倍圖．

1 星、扇、輪的倍圖的均勻色數

本文通過得到某個倍圖的均勻色數的下界k，然后給出一個k-均勻染色，從而得到這個倍圖的均勻色數．首先給出輪的倍圖的均勻色數．

定理1 對n+1階的輪Wn(n≥3)的倍圖D(Wn)，有

證明 記 n+1 階的輪 Wn(n≥3)為 V(Wn)={ui|i=0，1，2，…，n}，E(Wn)={u0ui|i=1，2，…，n}∪{uiui+1|i=1，2，…，n-1}∪{u1un}．由于 D(Wn)中含 u0的最大獨立集為 V0={u0，v0}，故若 f是1．以下分6種情形加以證明．

1)當 n=3 時，由于 D(W3)中含 ui的最大獨立集為{ui，vi}(i=0，1，2，3)，因此 χe(D(W3))≥4．下面給出 D(W3)的一個 4-均勻染色．令 f滿足 f(ui)=f(vi)=i，i=0，1，2，3，則|Vi|=2，i=0，1，2，3．并且對?uv∈E(D(W3))，均有 f(u)≠f(v)且||Vi|-|Vj||≤1(i，j∈{0，1，2，3})．所以，f是 D(W3)的一個4-均勻染色，故 χe(D(W3))=4．

2)當 n=4 時，含 u0的最大獨立集為{u0，v0}，而{u1，u2，u3，u4，v1，v2，v3，v4}在 D(W4)中的導出子圖為K4，4，故V(D(W4))無法劃分為4個獨立集，使得各個獨立集的頂點數相差不超過1，所以不存在D(W4)的 4-均勻染色．下面給出 D(W4)的一個 5-均勻染色．令 f滿足 f(ui)=f(vi)=i，i=0，1，2，3，4，則|Vi|=2，i=0，1，2，3，4．并且對?uv∈E(D(W4))，均有 f(u)≠f(v)且||Vi|-|Vj||≤1(i，j∈{0，1，2，3，4})．所以，f是 D(W4)的一個5-均勻染色，故 χe(D(W4))=5．

3)當n=5時，只需給出D(W5)的一個5-均勻染色．令f滿足f(u1)=f(v1)=f(u3)=1，f(u5)=f(v5)=f(v3)=2，f(u4)=f(v4)=3，f(u2)=f(v2)=4，f(u0)=f(v0)=0，則|V1|=|V2|=3;|V3|=|V4|=|V0|=2．并且對?uv∈E(D(W5))，均有 f(u)≠f(v)且||Vi|-|Vj||≤1(i，j∈{0，1，2，3，4})．所以，f是D(W5)的一個5-均勻染色，故χe(D(W5))=5．

4)當n=3k(k≥2)時，只需給出D(Wn)的=f(uk+i)=f(u2k+i)=i，i=1，2，3，…，k，f(vj)=f(vk+j)=f(v2k+j)=k+j，j=1，2，3，…，k，則|Vi|=3，i=1，2，3，…，2k，|V0|=2．并且對?uv∈E(D(Wn))，均有 f(u)≠f(v)且||Vi|-|Vj||≤1(i，j∈{0，1，2，

推論1 對n+1階的扇Fn(n≥2)的倍圖D(Fn)，有

1)當 n=2時，χe(D(F2))≥3．令 f滿足 f(u1)=f(v1)=1，f(u2)=f(v2)=2，f(u0)=f(v0)=0，則|Vi|=2，i=0，1，2．并且對?uv∈E(D(F2))，均有 f(u)≠f(v)且||Vi|-|Vj||≤1(i，j∈{0，1，2})．所以，f是D(F2)的一個3-均勻染色，故χe(D(F2))=3．

2)當 n=3時，由定理1知，3≤χe(D(F3))≤χe(D(W3))=4．D(F3)中含 u0的最大獨立集為{u0，v0}，含 u2的最大獨立集為{u2，v2}，因此，χe(D(F3))≥4，故 χe(D(F3))=4．

3)當 n=4 時，4≤χe(D(F4))≤χe(D(W4))=5．令 f滿足 f(u2)=f(v2)=f(u4)=1，f(u3)=f(v3)=f(v1)=2，f(u1)=f(v4)=3，f(u0)=f(v0)=0，則 |V0|=|V3|=2，|V1|=|V2|=3．并且對?uv∈E(D(F4))，均有 f(u)≠f(v)且||Vi|-|Vj||≤1(i，j∈{0，1，2，3})．所以，f是 D(F4)的一個 4-均勻染色，故 χe(D(F4))=4．

推論2 對n+1階的星Sn的倍圖D(Sn)，有

2 棱柱Lm的倍圖的均勻色數

對于簡單圖 G，u11u12…u1mu11，u21u22…u2mu21是 G 中 2 個不相交的圈，u1i與 u2i(i=1，2，…，m)分別相鄰，除此之外沒有多余的邊，則稱G為m-棱柱，記為Lm．

定理2 對Lm(m≥3)的倍圖D(Lm)，有

證明 記棱柱 Lm為 V(Lm)={u1i|i=1，2，…，m}∪{u2i|i=1，2，…，m}，E(Lm)={u1iu1i+1|i=1，2，…，m-1}∪{u1mu11}∪{u2iu2i+1|i=1，2，…，m-1}∪{u2mu21}∪{u1iu2i|i=1，2，…，m}．以下對 m 分奇偶進行討論．

1)m≡1(mod 2)．D(Lm)包含奇圈，所以 χ(D(Lm))≥3，從而 χe(D(Lm))≥χ(D(Lm))≥3．以下分 3種情況進行討論．

①m≡0(mod 3)．令f滿足

結合以上3種情形可得:當m≡1(mod 2)時，χe(D(Lm))=3．

2)m≡0(mod 2)．易知 D(Lm)為二部圖，其中 V((D(Lm))=(X，Y;E)的二分劃為 X={u1i，u2j，v1i，v2j|i=1，3，5，…，m-1，j=2，4，6，…，m}，Y={u1j，u2i，v1j，v2i|i=1，3，5，…，m-1，j=2，4，6，…，m}，故χe(D(Lm))=2．定理2 證畢．

［1］Erd?s P．Extremal problems in graph theory［C］//Miroslav F．Theory of graphs and its applications．NewYork:Prague Pub，1964:29-36．

［2］Hajnal A，Szemeredi E．Proof of a conjecture of Erd?s［C］//Erd?s P，Renyi A，Sos V T．Combinatorial theory and its applications，VolⅡ．Amsterdam:Bolyai Janos Matematikai Tarsulat，1970:601-603．

［3］Meyer W．Equitable coloring［J］．Amer Math Monthly，1973，80(8):920-922．

［4］Chen B L，Lih K W，Wu P L．Equitable coloring and the maximum degree［J］．European J Combin，1994，15(5):443-447．

［5］Zhang Yi，Yap H P．The equitable Δ-coloring conjecture holds for outerplanar graphs［J］．Bull Inst Math Acad Sinica，1997，25(2):143-149．

［6］Kostochka A V．Equitable coloring of outerplanar graph［J］．Discrete Math，2002，258(1/2/3):373-377．

［7］Zhang Yi，Yap H P．Equitable colorings of outerplanar graph［J］．J Combin Math Combin Comput，1998，27(3):97-105．

［8］Bondy J A，Murty U S R．Graph theory with applications［M］．London:Macmillan，1986．