ImCn的循環(huán)區(qū)間全著色

張澤堃，亢 明，趙永強

（1.河北地質(zhì)大學(xué) 數(shù)理學(xué)院，河北 石家莊 050031；2.中國地質(zhì)大學(xué)（北京）數(shù)理學(xué)院，北京 100083）

0 引言

首先介紹一些概念與符號.用V（G）和E（G）表示圖G的頂點集和邊集.對于頂點vV（G），用dG（v）表示v的度，用Δ（G）表示G的最大度.

用|A|表示有限集A的元素個數(shù).任意非空的由連續(xù)整數(shù)構(gòu)成的集合稱為區(qū)間.最小和最大元素分別為x和y的區(qū)間記作[x，y].由區(qū)間[x，y]中所有偶數(shù)構(gòu)成的集合與所有奇數(shù)構(gòu)成的集合分別記作e[x，y]和o[x，y].如果|M|=k，則稱區(qū)間|M|為k-區(qū)間.

圖的全著色概念分別由Vizing[1]與Behzad[2]獨立提出.

定義1[1，2]圖G的t-全著色為映射α：E（G）∪V（G）→[1，t]，使得任意相鄰的頂點、相鄰的邊以及相互關(guān)聯(lián)的頂點和邊均著色不同.

對于圖G的全著色α以及任意頂點vV（G），令S[α，v]={α[v]}∪{α[e]|e與v關(guān)聯(lián)}.最近文獻[3-5]推廣了圖的區(qū)間著色[6，7]以及區(qū)間全著色[8，9]概念，定義并研究了圖的循環(huán)區(qū)間全著色.

定義2[3]如果圖G的t-全著色α滿足下列條件：對任意xV（G），集合S[α，v]為[dG（v）+1]-區(qū)間，或者{1，t}S[α，v]為[t-dG（v）-1]-區(qū)間.則稱α為G的循環(huán)區(qū)間t-全著色.

如果存在某個整數(shù)t，使得圖G有一個循環(huán)區(qū)間t-全著色，則稱G為可循環(huán)區(qū)間全著色的.所有可循環(huán)區(qū)間全著色的圖構(gòu)成的集合記作F.

對于任意圖GF，其循環(huán)區(qū)間全著色所需最少與最多顏色數(shù)分別記作和.

2016年，王楠楠[3]研究了路Pn、圈Cn、輪圖Wn、完全圖Kn、完全二部圖Km，n以及完全三部圖K1，m，n的循環(huán)區(qū)間全著色.2017年，Zhao等[4]研究了圈Cn以及圈的中間圖M（Cn）的循環(huán)區(qū)間全著色.2018年，Su等[5]研究了圈的單點結(jié)合圖的循環(huán)區(qū)間全著色.

定義3[10]圖G和H的并記作G∪H，其頂點集為V（G）∪V（H），邊集為E（G）∪E（H）.如果G和H不相交，則稱其并為不交并，記作G+H.從圖G和H的不交并開始，將G中的每個頂點與H的任一頂點連接，得到的圖稱為G和H的聯(lián)圖，記作GH.

注意到輪圖其實就是一個孤立頂點與圈的聯(lián)圖，孤立頂點就是僅有一個頂點的空圖.所以空圖Im與圈Cn的聯(lián)圖ImCn（m≥1，n≥3）可視為輪圖Wn的推廣.筆者研究ImCn的循環(huán)區(qū)間全著色，文中用到但未詳細說明的圖論概念見文獻[10，11].為了方便，令V（Im）={u1，u1，…，um}，V（Cn）={v1，v1，…，vn}，其中m≥1，n≥3.

2016年，王楠楠研究了輪圖Wn的循環(huán)區(qū)間全著色，并得到如下結(jié)果.

定理1[3]當整數(shù)n≥4時，有WnF，并且

由于Wn=I1Cn-1，所以由定理1立即可得下面的結(jié)果.

推論1當整數(shù)n≥3時，有I1CnF，并且.

引理1對于任意整數(shù)m≥2，如果n=m+1，則有ImCnF，并且=n+2.

證明：假設(shè)整數(shù)m≥2并且n=m+1.下面分兩種情況討論.

情形1：m為奇數(shù).

構(gòu)造ImCn的一個（n+2）-全著色α.令

I3C4的6-全著色如圖1所示.

圖1 I3C4的6-全著色

根據(jù)α的定義可知：S[α，ui]=[1，m+2]，i[1，m]；S[α，vj]=[1，m+3]，j[1，m+1].這就證明α是ImCn的一個循環(huán)區(qū)間（n+2）-全著色，并且有≤n+2.

情形2：m為偶數(shù).

構(gòu)造ImCn的一個（n+2）-全著色α.令

重新把umv2著色為α（umv2）=n+2.I4C5的7-全著色如圖2所示.

圖2 I4C5的7-全著色

根據(jù)α的定義可知S[α，ui]=[2，n+2]，i[1，m]；S[α，vj]=[1，n+2]，j[1，n].這就證明α是ImCn的一個循環(huán)區(qū)間（n+2）-全著色，并且有≤n+2.

綜合情形1和2可知，當m≥2并且n=m+1時，有ImCnF，并且≤n+2.另一方面，由于此時⊿（ImCn）=n+1，所以有+1=n+2.因此=n+2.

引理2對于任意整數(shù)m≥2，如果n=m+2，則有ImCnF，并且當m為偶數(shù)時，有=n+1；當m為奇數(shù)時，有≤n+2.

證明：假設(shè)整數(shù)m≥2并且n=m+2.下面分兩種情況來討論.

情形1：m為偶數(shù).

I2C4的一個循環(huán)區(qū)間5-全著色如圖3所示.

圖3 I2C4的5-全著色

下面構(gòu)造ImCn（m≥4）的一個（n+1）-全著色α.令

I4C6的7-全著色如圖4所示.

圖4 I4C6的7-全著色

根據(jù)α的定義可知S[α，ui]=S[α，vj]=[1，n+1]，i[1，m]，j[1，n].這就證明α是ImCn的一個循環(huán)區(qū)間（n+1）-全著色，并且有

情形2：m為奇數(shù).

構(gòu)造ImCn的一個（n+2）-全著色α.令

I3C5的7-全著色如圖5所示.

圖5 I3C5的7-全著色

根據(jù)α的定義可知S[α，ui]=[1，n+1]，i[1，m]；S[α，vj]=這就證明α是ImCn的一個循環(huán)區(qū)間（n+2）-全著色，并且有

由于此時⊿（ImCn）=n，所以有+1=n+1.綜合情形1和2可知，結(jié)論成立.

引理3對于任意整數(shù)m≥2，如果n≥m+3，則有ImCnF，并且=n+1.

證明：假設(shè)整數(shù)m≥2并且n≥m+3.下面分兩種情況討論.

情形1：m為奇數(shù).

構(gòu)造ImCn的一個（n+1）-全著色α.令

I3C7的8-全著色如圖6所示.

圖6 I3C7的8-全著色

根據(jù)α的定義可知S[α，ui]=[1，n+1]，i[1，m]；

是ImCn的一個循環(huán)區(qū)間（n+1）-全著色，并且有

情形2：m為偶數(shù).

構(gòu)造ImCn的一個（n+1）-全著色α.令

I4C7的8-全著色如圖7所示.

圖7 I4C7的8-全著色

根據(jù)的定義可知S[α，ui]=[1，n+1]，i[1，m]；

ImCn的一個循環(huán)區(qū)間（n+1）-全著色，并且有

綜合情形1和2可知，當m≥2并且n≥m+3時，有ImCnF，并且≤n+1.另一方面，由于此時⊿（ImCn）=n，所以有.因此

綜合引理1～3可得下面結(jié)果.

定理2對于任意整數(shù)n＞m≥2，有ImCnF，并且：1）當n=m+1時，=n+2；2）當n=m+2且m為奇數(shù)時，n+1≤n+2；3）當n≥m+3，或當n=m+2且m為偶數(shù)時，=n+1.

定理3對于任意整數(shù)m≥n≥3，有

證明：假設(shè)整數(shù)m，n滿足m≥n≥3.首先給出ImCn的頂點和邊的一個（m+3）-著色α.令

注意：根據(jù)α的定義，一方面，當i[1，m-n+1]或i[m-n+3，m-1]時，有α（ui+1）=α（ui）+1且α（u1）=n+1，α（um-n+3）=m-n+4；另一方面，α（v1）=m-n+3且當j[2，n-1]時，有α（vj+1）=α（vj）+1且α（vn）=n-1.下面分情況進行討論.

情形1：m=2n-3.

一方面，min{α（ui）|i[1，m-n+2]}=α（u1）=n+1，min{α（ui）|i[m-n+3，m]}=α（um-n+3）=n+1.

另一方面，α（v1）=m-n+3=n，max{α（vj）|j[2，n]}=α（vn）=n-1.

從而對于任意i[1，m]和j[1，n]，有α（ui）＞α（vj）.所以不難檢驗α為ImCn的一個（m+3）-全著色.I3C3的6-全著色如圖8所示.

圖8 I3C3的6-全著色

根據(jù)α的定義可知

所以α是ImCn的一個循環(huán)區(qū)間（m+3）-全著色.

情形2：m=2n-4.

因為3≤n≤m=2n-4，所以m≥n≥4.

一方面，min{α（ui）|i[1，m-n+2]}=α（u1）=n+1，min{α（ui）|i[m-n+3，m]}=α（um-n+3）=n.

另一方面，α（v1）=m-n+3=n-1，max{α（vj）|j[2，n]}=α（vn）=n-1.

可以注意到，雖然對于任意i[1，m]和j[1，n]，α（ui）＞α（vj）仍成立，但此時有α（v1）=α（vn）=n-1.為此把vn和um-n+3vn分別重新著色為α（vn）=1和α（um-n+3vn）=n-1.不難檢驗，此時α為ImCn的一個（m+3）-全著色.I4C4的7-全著色如圖9所示.

圖9 I4C4的7-全著色

根據(jù)α的定義有

所以α是ImCn的一個循環(huán)區(qū)間（m+3）-全著色.

情形3：m≤2n-5.

因為3≤n≤m≤2n-5，所以m≥n≥5且有α（um-n+3）=m-n+4≤n-1=α（vn）.從而有：

對于任意j[m-n+5，n]，把vj和un-1vj分別重新著色為α（vj）=j-m+n-3和α（un-1vj）=j-1.此時S[α，un-1]=[m-n+4，m+3]∪{1}且對于任意wV（ImCn){un-1}，S[α，w]保持不變.

注意此時α（vn）=2n-m-3.如果仍有α（um-n+3）=m-n+4≤2n-m-3=α（vn），即：

則對于任意j[2m-2n+7，n]，把vj和u2n-m-3vj分別重新著色為α（vj）=j-2m+2n-5和α（un-1vj）=j-m+n-3.此時S[α，u2n-m-3]=[m-n+4，m+3]∪{1}且對于任意wV（ImCn){u2n-m-3}，S[α，w]保持不變.

注意此時α（vn）=3n-2m-5.如果仍有α（um-n+3）≤α（vn），則重復(fù)上面過程，直至α（um-n+3）＞α（vn）為止.

如果上述過程結(jié)束后有α（v1）=α（vn），則重復(fù)情形2的操作.不難檢驗，此時α為ImCn的一個循環(huán)區(qū)間（m+3）-全著色.I5C5的8-全著色如圖10所示.

圖10 I5C5的8-全著色

情形4：m≥2n-2.

因為m≥2n-2，所以α（um-n+3）=m-n+4≥n+2.又因為α（u1）=n+1，α（vn）=n-1，所以對于任意i[1，m]與j[2，n]，總有α（ui）＞α（vj）.一方面，因為m≥2n-2，所以α（v1）=m-n+3≥n+1=α（u1）.另一方面，因為n≥3，所以α（v1）=m-n+3≤m=α（um-n）.由于α（uk）在[1，m-n]上是遞增的，所以存在k[1，m-n]，使得α（v1）=α（uk）.

子情形4.1：k=1.

即α（v1）=α（u1）.把u1重新著色為α（u1）=m+3.此時不難驗證α為ImCn的一個（m+3）-全著色.根據(jù)α的定義有S[α，u1]=[1，n]∪{m+3}且對于任意wV（ImCn){u1}，S[α，w]保持不變.所以為α為ImCn一個循環(huán)區(qū)間（m+3）-全著色.I4C3的7-全著色如圖11所示.

圖11 I4C3的7-全著色

子情形4.2：k=2.

即m-n+3=α（v1）=α（u2）=n+2，也即m=2n-1.當n=3時，m=5.把I5C3重新著色如下.令

再重新把u3v3，u4v3以u5v3及分別著色為α（u3v3）=2，α（u4v3）=5，α（u5v3）=1.不難檢驗α為I5C3的一個8-全著色.根據(jù)α的定義可知S[α，u1]=[1，3]∪{8}，S[α，u2]=S[α，u3]=[2，5]，S[α，u4]=[5，8]，S[α，u5]=[6，8]∪{1}，S[α，vj]=[1，8]，j[1，3].

所以α為I5C3的一個循環(huán)區(qū)間8-全著色.I5C3的循環(huán)區(qū)間8-全著色如圖12所示.

圖12 I5C3的8-全著色

當n≥4時，m≥7.把v1，u2以及v1u2重新著色為α（v1）=2，α（u2）=m-n+4=n+3，α（v1u2）=m-n+3=n+2.不難檢驗α為ImCn的一個（m+3）-全著色.此時S[α，u2]=[3，n+3]且對于任意wV（ImCn){u2}，S[α，w]保持不變.所以α為ImCn的一個循環(huán)區(qū)間（m+3）-全著色.I7C4的10-全著色如圖13所示.

圖13 I7C4的10-全著色

子情形4.3：k[3，m-n].

即m-n+3=α（v1）=α（uk）=k+n，這里k[3，m-n].

如果k=n-1=α（vn）.則把v1和v1uk-1分別重新著色為α（v1）=k-1和α（v1uk-1）=m-n+3=k+n.此時不難檢驗為α為ImCn的一個循環(huán)區(qū)間（m+3）-全著色.根據(jù)α的定義可知S[α，uk-1]=[k，k+n]且對于任意wV（ImCn){uk-1}，S[α，w]保持不變.所以α為ImCn的一個循環(huán)區(qū)間（m+3）-全著色.I8C4的循環(huán)區(qū)間11-全著色如圖14所示.

圖14 I8C4的11-全著色

如果k≠n-1=α（vn）.則把v1，uk以及v1uk分別重新著色為α（v1）=k，α（uk）=m-n+4=k+n+1和α（v1uk）=m-n+3=k+n.此時不難檢驗α為ImCn的一個（m+3）-全著色.根據(jù)α的定義可知S[α，uk]=[k+1，k+n+1]且對于任意wV（ImCn){uk}，S[α，w]保持不變.所以α為ImCn的一個循環(huán)區(qū)間（m+3）-全著色.I6C3的9-全著色如圖15所示.

圖15 I6C3的9-全著色

綜合子情形4.1～4.3，當m≥2n-2時，ImCn存在一個循環(huán)區(qū)間（m+3）-全著色.

綜合情形1～4，當m≥n≥3時，ImCnF且w（ImCn)≤m+3.另一方面，由于⊿（ImCn）=m+2，所以有.因此

3 總結(jié)

研究了空圖Im與圈Cn的聯(lián)圖ImCn的循環(huán)區(qū)間全著色，證明對于任意整數(shù)m≥2，n≥3，ImCn均為可循環(huán)區(qū)間全著色的，并且得到如下結(jié)果：

1）當n=m+1時；

2）當n=m+2且m為奇數(shù)時，n+1≤

3）當n≥m+3，或當n=m+2且m為偶數(shù)時，

4）當m≥n時，

雖然如此，當n=m+2且m≥2為奇數(shù)時，的準確值還沒能確定.另外，關(guān)于的取值也有待研究.