正則圖的均勻邊染色

于罡，宋海洲

（華僑大學(xué)數(shù)學(xué)科學(xué)學(xué)院，福建 泉州 362021）

正則圖的均勻邊染色

于罡，宋海洲

（華僑大學(xué)數(shù)學(xué)科學(xué)學(xué)院，福建 泉州 362021）

研究正則圖的均勻邊染色，指出并非所有正則圖都存在任意種顏色的均勻邊染色.證明當(dāng)l能夠分解為整數(shù)k與偶數(shù)b的乘積時，l-正則圖存在均勻k-邊染色.同時，給出正則圖均勻邊染色的最小顏色數(shù).

正則圖；邊染色；均勻邊；幾乎均勻邊

圖的染色問題是圖論研究的經(jīng)典領(lǐng)域.這是由于它在組合分析和實際生活中的廣泛需要，如時間表問題、貯藏問題、電信通訊站點的頻率分配問題、計算機網(wǎng)絡(luò)結(jié)構(gòu)設(shè)計區(qū)分問題，以及計算機和銀行安全密碼問題等.其中的一些網(wǎng)絡(luò)及優(yōu)化問題，可以進(jìn)一步轉(zhuǎn)化為均勻點染色、均勻邊染色、均勻全染色等問題.圖的染色的基本問題就是確定各種染色法的色數(shù)，而確定圖的有關(guān)色數(shù)是一個十分困難的問題.文［1］證明對于任意v∈V（G），若k不能整除d（v），則圖G存在均勻k-邊染色.文［2］證明了所有的二分圖都是可均勻染色的.文［3］證明了任意一個不為奇圈的連通外平面圖都是均勻可染的.文［4］給出了Halin圖的一些均勻邊染色結(jié)果.文［5］研究了混合超圖的星染色的若干性質(zhì).本文討論正則圖的均勻邊染色，考慮的圖都是有限無向簡單圖.

1 定義及引理

圖G的點集和邊集分別用V（G）和E（G）表示.對任意的v∈V（G），令dG（v）表示v的度，在不致引起混淆的情況下，簡記為d（v）.如果對每個v∈V（G），均有dG（v）=l，無向圖G稱為l-正則的.圖G的邊染色是給圖G的每條邊分配一種顏色，用正整數(shù)1，2，…表示顏色，若C是邊集E到集合｛1，2，…，k｝的映射，即C∶E→｛1，2，…，k｝，則稱C為圖G的k-邊染色［6］.令iC（v）表示在染色C中與G的頂點v關(guān)聯(lián)的i色邊的數(shù)目.在不致引起混淆的情況下，簡記i（v）=iC（v）.

定義1 假設(shè)C為圖G的k-邊染色，對于任意的v∈V（G）和任意的i，j∈｛1，2，…，k｝，如果|i（v）-j（v）|≤1，則稱C為圖G的均勻邊染色.如果|i（v）-j（v）|≤2，則稱C為圖G的幾乎均勻邊染色.

令E（i）表示圖G的邊染色C中i色邊組成的集合，E（i）∪E（j）的邊導(dǎo)出子圖記為G（i，j）.對任意的v∈V（G），令G（v.，i，j）表示G（i，j）中含頂點v的連通分支.

下面給出4個重要引理.

引理2［1］設(shè)圖G為簡單圖，k≥2.如果對任意v∈V（G），有d（v）?0（modk），則圖G存在k種顏色的均勻邊染色.

引理3［8］設(shè)圖G為連通圖，則圖G一定存在2-邊染色C，其滿足以下3個條件：（1）若圖G為歐拉圖且|E|為奇數(shù)，則對V中任意選取的頂點u，有|1（u）-2（u）|=2.對于所有的v∈V（G）｛u｝，均有1（v）-2（v）=0.（2）若圖G為歐拉圖且|E|為偶數(shù)，則對于所有的v∈V（G），有1（v）-2（v）=0.（3）若圖G不是歐拉圖，則對所有的v∈V（G），有|1（v）-2（v）|≤1.

引理4［7］設(shè)k為大于1的任意整數(shù)，則存在圖G的k-邊染色C，使得對任意v∈V（G），i，j∈｛1，2，…，k｝，有|i（v）-j（v）|≤2.

設(shè)k≥1，C為圖G的幾乎均勻k-邊染色.對任意的v∈V（G），令

顯然，對圖G的均勻邊染色有σ（C）=0.

若圖G中的鏈K=（v0，e1，v1，e2，…，vr-1，er，vr）滿足如下的條件，則稱K為圖G由v0發(fā)出的一條（α，β）-交換鏈.

（i）對任意的1≤i≤r，頂點vi-1和vi是邊ei的兩個不同端點；

（ii）K中所有的邊互異，且交替染以α色和β色；

（iii）e1染α色，且α（v0）＞β（v0）.

類似地，令γ記邊er的顏色，γˉ記｛α，β｝中的另一種顏色，則γ（vr）＞γˉ（vr）.

若圖G由v0發(fā)出的一條（α，β）-交換鏈以一條β色邊到達(dá)v0，則再從一條與v0關(guān)聯(lián)的還沒有在交換鏈上出現(xiàn)的α色邊開始，繼續(xù)找下去.這條（α，β）-交換鏈的終點vr可能與始點v0相同.

令K為一條由頂點發(fā)出的（α，β）-交換鏈，若不存在另一條由頂點發(fā)出的（α，β）-交換鏈K′?K，則稱K為由頂點x發(fā)出的極?。é?，β）-交換鏈.

若α（v0）≥β（v0）+2，則通過交換K上的兩種顏色可能使染色更均勻；然而，若α（v0）=β（v0）+2且v0=vr，通過交換K上的兩種顏色并不能改善其染色.可以看出，交換交換鏈上的兩種顏色并不會使染色更壞.

2 主要結(jié)論

由引理2可知，當(dāng)l?0（modk）時，l-正則圖存在k種顏色的均勻邊染色.

下面討論一種l≡0（modk）的情形.

定理1 設(shè)l=bk，b為不小于2的偶數(shù)，則l-正則圖G存在k種顏色的均勻邊染色.

證明 由引理4可知，圖G存在k種顏色的幾乎均勻邊染色，在圖G的所有k種顏色的幾乎均勻邊染色中，令C為使σ（C）達(dá)到最小的染色.如果σ（C）=0，則C為均勻k-邊染色.

下面用反證法，假設(shè)σ（C）＞0，則存在x∈V（G）和α0，β∈｛1，2，…，k｝，使得α0（x）=β（x）+2.

考慮邊導(dǎo)出子圖G（x.，α0，β）.如果H（x.α0，β）是有奇數(shù)條邊的歐拉圖，滿足α0（x）=β（x）+2，并且對每個v∈V（H）｛x｝，均有α（v）=β（v）成立，則稱H為圖G在頂點x處的障礙子圖.

如果對某個x∈V（G），α0（x）=β（x）+2，但H=G（x.α0，β）不是障礙子圖，由引理3，可用顏色α0，β對H的邊重新染色，從而得到圖G的一個幾乎均勻邊染色C′，滿足σ（C′）＜σ（C），產(chǎn)生矛盾.

下設(shè)H=G（x.α0，β）為一個障礙子圖.另設(shè)y0為與x通過α0色邊關(guān)聯(lián)的一點，記邊（x，y0）=e0.

因為C為幾乎均勻邊染色，易知對任意v∈V（G），i∈｛1，2，…，k｝，必有i（v）∈｛b-1，b，b+1｝.若存在i∈｛1，2，…，k｝，使得i（v）=b-1，則必存在j∈｛1，2，…，k｝，使得j（v）=b+1成立，反之亦然.這樣，障礙子圖H=G（x.α0，β）中，必有α0（x）=b+1，β（x）=b-1.

情形1 α0（y0）=β（y0）=b+1，則存在α1∈｛1，2，…，k｝使得α1（y0）=b-1.

首先將邊e0重新染以β色.在圖G的當(dāng)前染色中，α0（x）=β（x）=b，且β（y0）=b+2，α0（y0）=b.記由y0發(fā)出的（β，α1）極小交換鏈為K.如果K不終止于y0，則交換K中邊的顏色后，β（y0）=b+1，α1（y0）=α0（y0）=b；如果K終止于y0本身，則交換K中邊的顏色后，β（y0）=α0（y0）=b，α1（y0）=b+1.這樣一來，每種情況都得到了圖G的仍為幾乎均勻邊染色的染色C′，且σ（C′）＜σ（C）.

情形2 α0（y0）=β（y0）=b-1.存在α1∈｛1，2，…，k｝，使得α1（y0）=b+1.將邊e0重新染以β色.在圖G的當(dāng)前染色中，α0（x）=β（x）=b，且β（y0）=b，α0（y0）=b-2.記由y0發(fā)出的（α1，α0）極小交換鏈為K.如果K不終止于y0，交換K中邊的顏色后，α1（y0）=b，α0（y0）=b-1，β（y0）=b，圖G得到改進(jìn)，產(chǎn)生矛盾.如果K終止于y0本身，交換K中邊的顏色后，α1（y0）=b-1，α0（y0）=b，β（y0）=b，圖G同樣得到改進(jìn)，產(chǎn)生矛盾.

情形3 α0（y0）=β（y0）=b，頂點x通過α0色邊相關(guān)聯(lián)的任意點，均有α0（v）=β（v）=b.不然，由情形1，2可知，對染色改進(jìn)，產(chǎn)生矛盾.

顯然，由x點發(fā)出的（α0，β）極小交換鏈K必以一條α0色邊終止于x本身；否則，交換K中邊的顏色，在新染色中，α（x）=β（x）=b，C得到改進(jìn)，產(chǎn)生矛盾.

x點通過β色邊關(guān)聯(lián)的任意點v，必有α0（v）=β（v）=b.不然，α0（v）=β（v）=b+1或α0（v）=β（v）=b-1，則可以交換K中邊的顏色，在新染色中α（x）=b-1=β（x）-2.此時，障礙子圖為G（x.，β，α0）.

由情形1，2的討論可知，對圖G的當(dāng)前染色改進(jìn)，產(chǎn)生矛盾.這樣，得出H=G（x.，α0，β）中與x關(guān)聯(lián)的任意點，均有α0（v）=β（v）=b.將e0重新染以β色，在圖G的當(dāng)前染色中，有

α0（x）=β（x）=b，

β（y0）=b+1=α0（y0）+2.

在此情形下，圖H中任意點的度均為2b.假設(shè)圖H的階為q，因為b是偶數(shù)，則由引理1可知，|E（H）|=2b·q/2=b·q為偶數(shù)，與障礙子圖的定義矛盾.證畢.

實際上，當(dāng)l=bk，b為奇數(shù)時，l-正則圖未必是可以均勻k-邊染色的.例如，b=1，k=4時的完全圖K5，就不存在4種顏色的均勻邊染色；而b=3，k=2的奇數(shù)階l-正則圖，也不存在2種顏色的均勻邊染色.

由文［2］知，當(dāng)正則圖可以2部劃分時，其存在任意種顏色的均勻邊染色.

綜上所述，得到如下的推論.

推論1 并非所有正則圖都存在任意種顏色的均勻邊染色.

由引理2可知，任意簡單圖G都存在Δ（G）+1種顏色的均勻邊染色，其中

Δ（G）=max｛dG（x）∶x∈V（G）｝.

對于給定的簡單圖G，定義

χ″（G）=min｛k∶G存在k（k＞1）種顏色的均勻邊染色｝，

顯然，χ″（G）是有意義的.

定理2 設(shè)圖G為連通的m階l-正則圖，則

（i）χ″（G）=3，當(dāng)l=2（2s+1），其中s為非負(fù)整數(shù)，且m為奇數(shù)；

（ii）χ″（G）=2，其他情況.

證明 （1）若l為奇數(shù)，由引理2可知，χ″（G）=2；

（2）若l≡0（mod 4），由引理1可知，|E（G）|=ml/2為偶數(shù)，再由引理3可得，χ″（G）=2；

（3）若l?0（mod 4），但l≡0（mod 2）且m為偶數(shù)，則|E（G）|亦為偶數(shù)，由引理3可知，χ″（G）=2.至此，證得定理2的（ii）情形.

下面討論定理2的（i）情形.此時，圖G為歐拉的且有奇數(shù)條邊.

首先，證明χ″（G）≠2.在圖G的任意2k-邊染色C中，由|E（G）|為奇數(shù)，可知E（1）≠E（2），所以至少存在一點，不妨設(shè)為v0，使得1（v0）≠2（v0）.圖G是歐拉圖，可知d（v0）是偶數(shù).又因為d（v0）=1（v0）+2（v0），所以必有|1（v0）-2（v0）|≥2，即C不是均勻邊染色.由C的任意性，可知圖G不存在2種顏色的均勻邊染色，即χ″（G）≠2.

其次，證明χ″（G）=3.若l?0（mod 3），則由引理2可知，圖G存在3種顏色的均勻邊染色，即有χ″（G）=3.若l≡0（mod 3），則l可以表示成l=6（2t+1）的形式，其中t為非負(fù)整數(shù).

由引理4可知，圖G存在一個幾乎均勻3-邊染色.在圖G的所有幾乎均勻3-邊染色中，令C為使σ（C）達(dá)到最小的染色.如果σ（C）=0，則C為均勻3-邊染色.

下面用反證法，假設(shè)σ（C）＞0，則存在v∈V（G）和α，β∈｛1，2，3｝，使得α（x）-β（x）=2.

如果邊導(dǎo)出子圖H=G（x.，α0，β）不是障礙子圖，則由引理3可知，用顏色α，β對圖H中的邊重新染色，得到滿足σ（C′）＜σ（C）的幾乎均勻邊染色C′，產(chǎn)生矛盾.

假設(shè)H=G（x.，α0，β）為障礙子圖.對于任意的y∈V（H）｛x｝，因為C是幾乎均勻邊染色，所以必有

α（y）=β（y）=2（2t+1），

α（x）=2（2t+1）+1，β（y）=2（2t+1）-1.

且

設(shè)圖H的階為q，則由引理1可知

|E（G）|為偶數(shù)，與障礙子圖的定義矛盾.從而定理2的情形（i）得證.證畢.

［1］HIL TON A J W，de WERRA D.A sufficient condition for equitable edge-coloring of simple graphs［J］.Discrete Mathematics，1994，128（1/3）：179-201.

［2］de WERRA D.Equitable colorations of graphs［J］.Reveu Francaise d’Informatique et de Recherche Operationelle，1971，5（3）：3-8.

［3］WU Jian-liang.The equitable edge-colouring of outerplanar graphs［J］.The Journal of Combinatorial Mathematics and Combinatorial Computing，2001，36（1）：247-253.

［4］宋慧敏，龍和平，吳建良.Halin圖的均勻邊染色［J］.山東大學(xué)學(xué)報：理學(xué)版，2003，38（2）：32-34.

［5］王志雄.混合超圖的星染色［J］.華僑大學(xué)學(xué)報：自然科學(xué)版，1996，17（2）：123-126.

［6］宋慧敏，劉桂真.圖的f-邊覆蓋染色［J］.數(shù)學(xué)學(xué)報，2005，48（5）：919-928.

［7］徐俊明.圖論及其應(yīng)用［M］.2版.合肥：中國科學(xué)技術(shù)大學(xué)出版社，2004：13.

［8］HAKIMI S L，KARIV O.A generalization of edge-coloring in graphs［J］.Journal of Graph Theory，1986，10（2）：139-154.

Equitable Edge-Coloring of Regular Graph

YU Gang，SON G Hai-zhou
（School of Mathematical Sciences，Huaqiao University，Quanzhou 362021，China）

The equitable edge-coloring of a regular graph is studied in this paper.It is shown that equitable edge-colorings with any colors can’t be done for all regular graphs.It is proved that al-regular graph has an equitable edge-coloring withkcolors whenl=kb，wherekandbare integer andbis even.Theminimum number of colors for a regular graph to have an equitable edge-coloring is given，too.

regular graph；edge coloring；equitable edge；nearly equitable edge

O 157.5

A

1000-5013（2010）06-0711-04

（責(zé)任編輯：陳志賢 英文審校：張金順，黃心中）

2008-12-12

宋海洲（1971-），男，副教授，主要從事運籌與控制的研究.E-mail：hzsong@hqu.edu.cn.

福建省自然科學(xué)基金資助項目（Z0511028）