關于圖Pa,b的鄰點可區別染色

嚴謙泰

(安陽師范學院 數學與統計學院，河南 安陽 455000)

1 研究背景

圖的染色是圖論的重要研究內容，由計算機科學和信息科學等所產生的一般點可區別邊染色[1]、鄰點可區別邊染色[2-6]、鄰點可區別全染色[7]、鄰點強可區別全染色[8]等染色法，這些都是十分困難的問題，至今文獻甚少。文中將通過具體的染色方法，給出圖Pa,b的鄰點可區別邊染色數、鄰點可區別全染色數、鄰點強可區別全染色數。

定義2[7]圖G(V,E)的一個正常全染色f:V∪E→{1,2,…,k}，如果滿足：

1)對任意的uv∈E有f(u)≠f(v),f(u)≠f(uv),f(v)≠f(uv);

2)對任意的uv,vw∈E有f(uv)≠f(vw)，且C(u)≠C(v)。

則稱f是圖G(V,E)的一個鄰點可區別全染色，簡記為k-AVETC。在k-AVDTC中最小的數k稱為圖G(V,E)的一個鄰點可區別全染色數，記為χat(G)=min{k|k-AVDTC}。

定義3[8]設G(V,E)是階數不小于3的簡單連通圖，f是從V(G)∪E(G)到{1,2,…,k}的映射，滿足:

1) 對任意的邊uv∈E(G)，f(u)≠f(v)，f(u)≠f(uv)，f(v)≠f(uv);

2)對任意的兩相鄰邊uv，uw∈E(G)(v≠w)，f(uv)≠f(uw);

3)對任意的邊uv∈E(G)，其端點的色集合滿足C(u)≠C(v)，其中一頂點u的色集合

C(u)={f(u)}∪{f(v)|uv∈E(G)}

∪{f(uv)|uv∈E(G)}

則稱f是圖G的一個鄰點強可區別的全染色，簡記作k-AVSDTC，且稱數

χast(G)={k|G所有的k-AVSDTC}

為G的鄰點強可區別的全染色數。

定義4[9]設u,v是兩個固定頂點，用b條內部互不相交且長度均為a的道路連接u,v的圖用Pa,b表示。

本文涉及的圖都是簡單連通有限圖，未加說明的術語與記號見文獻[10]。

2 主要結論及其證明

引理2[7]如果簡單圖G是階不小于3的圖，則χat(G)≥Δ(G)+1；如果簡單圖G有兩個相鄰的最大度頂點，則χat(G)≥Δ(G)+2。

引理3[8]如果簡單圖G是階不小于3的圖，則χast(G)≥Δ(G)+1;而G中至少有最大度頂點相鄰，則有χast(G)≥Δ(G)+2。

引理4[8]對于n階路Pn(n≥3)，有

χast(Pn)={4,n≡0(mod 2)

5,n≡1(mod 2)

……

即第1條路上的邊用1,2,…,b循環染色；第2條路上的邊用2,3,…,b，1循環染色；第3條路上的邊用3,4,…,b，1，2循環染色；……；第b條路上的邊用b，1,2,…,b-1循環染色。這是Pa,b的一個b-AVDEC。

定理2 對于圖Pa,b(a≥3,b≥3)，有χat(Pa,b)=b+1。

證明 情形1 對于圖Pa,3(a≥3)，有χat(Pa,3)=4。

由于Δ(Pa,3)=3，由引理2知，χat(Pa,b)≥4，下證χat(Pa,b)=4。Pa,3中每條路上一共有2a+1個頂點和邊。

故f是Pa,3的4-AVDTC。

故f是Pa,3的4-AVDTC。

綜上可知，χat(Pa,3)=4。

情形2 對于圖Pa,b(a≥3,b≥4)，由于Δ(Pa,b)=b，故χat(Pa,b)≥b+1，下證χat(Pa,b)=b+1。Pa,b(a≥3,b≥3)中每條路上一共有2a+1個頂點和邊。

第1條路上前2a個頂點和邊用1,2,…,b,b+1循環染色；

第2條路上的頂點和邊用1，3，4，…，b+1，2循環染色；

第3條路上的頂點和邊用1，4，5，…，b+1，2，3循環染色；

……

第b條路上的頂點和邊用1,b+1,2,3,…,b循環染色。

這是Pa,b的一個(b+1)-AVDTC。

……

這是Pa,b的一個(b+1)-AVDTC。

……

這是Pa,b的一個(b+1)-AVDTC。

一般地，當2a+1≡i(mod(b+1))時，

……

……

綜上可知，f是Pa,b的一個(b+1)-AVDTC。

定理3 對于圖Pa,3(a≥4)，有

χast(Pa,3)={4,a≡0(mod 2)

5,a≡1(mod 2)

情形1.1 當a≡0(mod 3)時，此時2a是3的倍數。

當i≡1(mod 2)時：

當i≡1(mod 2)時：

當i≡1(mod 2)時：

這是Pa,3(a≥4)的一個4-AVSDTC。

情形1.2 當a≡1(mod 3)時。

當i≡1(mod 2)時：

當i≡1(mod 2)時：

當i≡1(mod 2)時：

這是Pa,3(a≥4)的一個4-AVSDTC。

情形1.3 當a≡2(mod 3)時。

當i≡1(mod 2)時：

當i≡1(mod 2)時：

當i≡1(mod 2)時：

這是Pa,3(a≥4)的一個4-AVSDTC。

情形2.1 當a≡0(mod 5)時，

這是Pa,3(a≥4)的一個5-AVSDTC。

情形2.2 當a≡1(mod 5)時，

這是Pa,3(a≥4)的一個5-AVSDTC。

情形2.3 當a≡2(mod 5)時，

這是Pa,3(a≥4)的一個5-AVSDTC。

情形2.4 當a≡3(mod 5)時，

這是Pa,3(a≥4)的一個5-AVSDTC。

情形2.5 當a≡4(mod 5)時，

這是Pa,3(a≥4)的一個5-AVSDTC。

綜上可知，χast(Pa,3)={4,a≡0(mod 2)

5,a≡1(mod 2)。

定理4 對于圖Pa,b(a≥4,b≥4)，有χast(Pa,b)=b+1。

情形1 當a≡0(mod 5)時。

第i條路上的頂點用1(i+1)(i+2)(i+3)(i+4)循環染色，i=1,2,…,b，其中i+1，i+2，i+3，i+4(≥b+2)是在模b(modb)的意義下。 第i條路上的邊用(i+2)(i+3)(i+4)1(i+1)循環染色。同定理3可驗證f是Pa,b(a≥4,b≥4)的一個(b+1)-AVSDTC。

情形2 當a≡1(mod 5)時。

情形3 當a≡2(mod 5)時。

第i條路上的頂點用1(i+1)(i+2)(i+3)(i+4)循環染色，i=1,2,…,b，其中i+1，i+2，i+3，i+4(≥b+2)是在b(modb)模的意義下。 第i條路上的邊用(i+2)(i+3)(i+4)1(i+1)循環染色?？沈炞Cf是Pa,b(a≥4,b≥4)的一個(b+1)-AVSDTC。。

情形4 當a≡3(mod 5)時。

情形5 當a≡4(mod 5)時。

綜上可知，對圖Pa,b(a≥4,b≥4)，有χast(Pa,b)=b+1。