關(guān)于圈圖Cn的連3距k著色計數(shù)

薛展充

（澳門培正中學(xué)，澳門）

關(guān)于圈圖Cn的連3距k著色計數(shù)

薛展充

（澳門培正中學(xué)，澳門）

研究圈圖Cn的連3距k著色計數(shù)問題，根據(jù)圖的特征及基本計數(shù)原理建立若干聯(lián)立遞推關(guān)系，由此得到關(guān)于圈圖Cn的連3距k著色方法數(shù)的遞推關(guān)系.

圈；路；圖的連3距k著色

0 引言

對圖G的每個頂點都指定一種顏色，使得沒有兩個相鄰的頂點指定為相同的顏色.如果這些顏色選自于一個有k（k≥3）種顏色的集合而不管k種顏色是否都用到，這樣的著色稱為k著色[1].

圖的染色計數(shù)問題已有很多研究結(jié)果，如棋盤的染色計數(shù)公式[2-5]，n棱傘圖的k著色計數(shù)公式[6]，圈圖的染色計數(shù)公式[7]，有公共頂點的圈的染色計數(shù)公式[8]，圈圖的連2距k著色計數(shù)公式[9]，本文擬進(jìn)一步對圈圖Gn的連3距k著色計數(shù)問題進(jìn)行研究，先給出以下定義.

定義1[10]圖G的一條途徑（或通道）是指一個有限非空序列W=ν0e1ν1e2ν2…enνn，它的項交替地為頂點和邊，使得對1≤i≤n，ei的端點是νi-1和νi，稱W是從ν0到νn的一條途徑，或一條（ν0，νn）途徑.ν0和νn分別稱為W的起點和終點，而ν1，ν2，…，νn-1稱為它的內(nèi)部頂點.整數(shù)n稱為W的長.若途徑W的邊e1，e2，…，en互不相同，則W稱為跡.又若途徑W的頂點ν0，ν1，…，νn也互不相同，則W稱為路.長為n的路稱為n路，記為Ln.

定義2[10]G的兩個頂點u和ν稱為連通的，如果在G中存在（u，ν）路.若在G中頂點u和ν是連通的，則u和ν之間的距離dG（u，ν）是G中最短（u，ν）路的長.

定義3[10]稱一條途徑是閉的，如果它有正的長且起點和終點相同.若一條閉跡的起點和內(nèi)部頂點互不相同，則它稱為圈.長為n的圈稱為n圈，記為Cn.

定義4對圖G的每個頂點都指定一種顏色，使得任意距離不大于3的兩點均異色.如果這些顏色選自于一個有k（k≥4）種顏色的集合而不管k種顏色是否都用到，這樣的著色稱為圖G的連3距k著色.

以g3（k，G）表示圖G的連3距k著色的著色方法數(shù)，則g3（k，Gn）表示圈圖Cn（n≥4）的連3距k著色的著色方法數(shù).設(shè)圈圖Cn（n≥4）的n個頂點分別為A1，A2，A3，…，An，把Cn從頂點A1與頂點An之間割開，使成長為n-1的路Ln-1，則有g(shù)3（k，Ln-1）＝k（k-1）（k-2）（k-3）n-3，其中A1與An-2，An-1，An都異色且A2與An-1，An都異色且A3與An異色的著色方法數(shù)即為g3（k，Cn）.

g3（k，Ln-1）包括以下十五類情況（見表1）：

表1 g3（k，Ln-1）包含的十五類情況

易知an=g3（k，Cn），in=an-3.由對稱性，bn=cn=fn，dn=hn，en=kn，jn=ln，故

an+an-3+3bn+2dn+2en+gn+2jn+mn+on+pn=k（k-1）（k-2）（k-3）n-3，n≥7.

1 相關(guān)引理和定理

引理1設(shè)g3（k，Ln-1）中A1與An-2，An-1，An都異色的染色方法數(shù)為yn，則

證明g3（k，Ln-1）中A1與An-2，An-1，An，都異色即表1中的（1）至（5）類情況，由加法原理即得所證.

引理2 yn+yn-1+（k-3）yn-2+（k-3）2yn-3=k（k-1）（k-2）（k-3）n-3，n≥7.

證明把g3（k，Ln-1）分成下列四類：

（1）A1與An-2，An-1，An都異色，此時的染色方法數(shù)為yn；

（2）A1與An同色且A1與An-2，An-1都異色，此時的染色方法數(shù)為yn-1；

（3）A1與An-1同色且A1與An-2，An都異色，此時的染色方法數(shù)為（k-3）yn-2；

（4）A1與An-2同色且A1與An-1，An都異色，此時的染色方法數(shù)為（k-3）2yn-3.

由加法原理即得所證.

引理3 bn+gn+jn=（an-3+bn-3）（k-4）（k-3）+（bn-3+en-3+dn-3）（k-3）2，n≥7.

證明由對稱性，g3（k，Ln-1）中A1與An-2同色且An與A2，A3均無染色限制的染色方法數(shù)為bn+gn+jn，此染色方法數(shù)可分為下列五類（見表2）：

表2 bn+gn+jn包含的五類情況

由加法原理即得所證.

引理4 en+jn+mn=（an-2+2bn-2+dn-2+en-2）（k-3），n≥6.

證明由對稱性，g3（k，Ln-1）中A1與An-1同色且An與A2，A3均無染色限制的染色方法數(shù)為en+jn+mn，此染色方法數(shù)可分為下列五類（見表3）：

表3 en+jn+mn包含的五類情況

由加法原理即得所證.

引理5 on+pn=an-1+2bn-1+dn-1+en-1=yn-1，n≥5.

證明g3（k，Ln-1）中A1與An同色且A2與An-1染色限制的染色方法數(shù)為on+pn，此染色方法數(shù)可分為下列五類（見表4）：

表4 on+pn包含的五類情況

由加法原理即得所證.

引理6 dn=（k-4）an-3+（k-3）bn-3，n≥7.

證明把dn分成以下兩類：（1）A1與An-2同色且A2與An-1同色且A3與An-3異色，

此時的染色方法數(shù)為（k-4）an-3；（2）A1與An-2同色且A2與An-1同色且A3與An-3同色，此時的染色方法數(shù)為（k-3）bn-3.

由加法原理即得所證.

引理7 en=（k-4）（an-2-an-3）+（2k-7）（bn-2-bn-3）+（k-3）（dn-2-dn-3）+（k-3）en-2，n≥7.

證明由引理3至5及

由引理1，2可得

再由引理6即得所證.

引理8設(shè)an中滿足A1與An-3異色的染色方法數(shù)為qn，滿足A1與An-3同色的染色方法數(shù)為rn；設(shè)en中滿足A2與An-2異色的染色方法數(shù)為sn，滿足A2與An-2同色的染色方法數(shù)為tn，則

證明把bn分成以下十類（見表5）：

表5 bn包含的十類情況

由加法原理得

再由yn=an+2bn+dn+en，an=qn+rn，en=sn+tn，化簡得即得所證.

引理9 en=（k-4）yn-2+dn-2+en-2-qn-2-sn-2，n≥6.

把cn分成以下七類（見表6）：

由加法原理得

表6 cn包含的七類情況

再由yn=an+2bn+dn+en，an=qn+rn，en=sn+tn，化簡得即得所證.

引理10 bn=（k2-9k+20）an-3+（2k2-16k+31）bn-3+（k-3）（k-4）dn-3+（k-3）（k-4）en-3+（k-4）an-4+（2k-7）bn-4+（k-3）dn-4，n≥8.

證明由引理8，9化簡即得所證.

引理11 an，bn，yn滿足以下聯(lián)立遞推關(guān)系（n≥10）：

證明由引理1，2，6，7，10，通過加減消去法即得所證，過程較繁復(fù)，略.

定理1圈圖Cn的連3距k著色方法數(shù)an滿足以下遞推關(guān)系：

證明由引理11，通過加減消去法解聯(lián)立遞推關(guān)系可得所證，過程極為繁復(fù)，略.

至此本文得到關(guān)于圈圖Cn的連3距k著色方法數(shù)an的遞推關(guān)系，對于更高階的圈圖Cn的連m（m>3）距k著色問題，求解過程必更復(fù)雜，適當(dāng)利用計算器輔助及探求圖論新方法將是可取的.以下列出部分an值（見表7）.

表7 部分an值

[1]殷劍宏，吳開亞.圖論及其算法[M].合肥：中國科學(xué)技術(shù)大學(xué)出版社，2003：146.

[2]王躍進(jìn)，牛偉強.關(guān)于2×n方格的染色問題研究[J].中學(xué)數(shù)學(xué)育，2011（1）：47-48.

[3]顧紅俏.關(guān)于3×n棋盤的染色計數(shù)公式[J].新疆師范大學(xué)學(xué)報：自然科學(xué)版，2007，26（03）：90-92.

[4]盧家華，吳康.3×n方格染色問題的再研究[J].數(shù)學(xué)通報，2014，53（1）：61-63.

[5]張上偉，吳康.4×n棋盤的染色計數(shù)問題分析[J].汕頭大學(xué)學(xué)報：自然科學(xué)版，2013，28（02）：1-3.

[6]盧家華，凌明燦，吳康.n棱傘圖的k著色計數(shù)問題[J].汕頭大學(xué)學(xué)報：自然科學(xué)版，2014，29（02）：1-3.

[7]范思琪，吳康，李祥立.從一個圖論問題談高考與競賽的關(guān)系[J].澳門教育，2004，2：58-61.

[8]凌明燦，盧家華，吳康.有公共頂點的圈染色計數(shù)問題[C]//廣東省初等數(shù)學(xué)學(xué)會成立大會暨首屆學(xué)術(shù)研討會論文集.廣州：[出版者不詳].2014.

[9]吳康，薛展充.關(guān)于圈圖Cn的連2距k著色計數(shù)[J].華南師范大學(xué)學(xué)報：自然科學(xué)版，2007（2）：7-10.

[10]邦迪J A，默蒂U S R.圖論及其應(yīng)用[M].北京：科學(xué)出版社，1984：12-15.

Counting of Triple Distanced K-Coloring in Cycle

XUE Zhanchong
（Pui Ching Middle School,Macau,China）

The counting of triple distanced k-coloring in cycle is investigated.Some simultaneous recurrence relations are obtained according to the feature of the graph and fundamental counting principle.Thus，the recurrence relation about the counting of triple distanced k-coloring in cycle is obtained.

cycle；path；triple distanced k-coloring

O 167

A

1001-4217（2015）02-0056-06

2014-12-23

薛展充（1982-），男，澳門人，澳門培正中學(xué)高中數(shù)學(xué)老師.E-mail：sitsit_home@163.com