關于路的k-方圖的鄰點可區別-邊全染色和第一類弱全染色

嚴謙泰

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

1 研究背景

圖的染色問題具有重要的實際意義和理論意義。由計算機科學和信息科學等所產生的一般點可區別邊染色[1]、鄰點可區別邊染色[2-6]、鄰點可區別全染色[5]等都是十分困難的問題。在此基礎上，張忠輔等人提出了鄰點可區別-邊全染色[6]和第一類弱全染色的概念，并得到一些重要的結論。本文給出了路的k-方圖的鄰點可區別-邊全染色數和第一類弱全染色數。

定義1[3]圖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-AVDTC。在k-AVDTC中最小的數k稱為圖G(V,E)的一個鄰點可區別全染色數，記為χat(G)=min{k|k-AVDTC}。

定義2[6]對于簡單圖G(V，E)，若映射f:

V∪G→{1,2,…,k}滿足：

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

2)對任意的uv∈E有C(u)≠C(v)

則稱f是圖G(V,E)的一個鄰點可區別-邊全染色，簡記為k-AVD-ETC，且稱

為G的鄰點可區別-邊全染色數，其中色集合C(u)={f(u)}∪{f(uv)|uv∈E(G)}。

定義3[7]設G=(V,E)是階至少為2的連通圖。 映射f:V(G)∪E(G)→{1,2,…,k}，k是正整數。如果f滿足：

1)對任何uv∈E(G)有f(u)≠f(v)

2)對任何uv∈E(G)，vw∈E(G)，u≠v，有f(uv)≠f(vw)

則稱f為G的第一類弱全染色，簡記為FWTC，記χfwt(G)=min{k|k-FWTC}為G的第一類弱全染色數。

定義4 對于簡單圖G=(V,E),定義G的k-方圖Gk如下:

V(Gk)=V(G)

E(Gk)=E(G)∪{uv|d(u,v)=k，u,v∈V(G)}

其中k是一個大于1的正整數,d(u,v)表示u和v之間的距離。

2 主要結論

引理2[6]對任意的簡單圖G有

引理3[6]對于n階圈Cn有

引理4[7]對任意的簡單圖G有，χfwt(G)≥max{χ′(G),χ(G)}

f(vi)=1,i≡1(mod 2)

f(vi)=2,i≡0(mod 2)

f(vivi+1)=3,i=1,2,…,n-1

f(vivi+k)=3,i=1,2,…,n-k

情形2.1 當k≡1,2(mod 3)時，

f(vi)=1,i≡1(mod 3)

f(vi)=2,i≡2(mod 3)

f(vi)=3,i≡0(mod 3)

f(vivi+1)=4,i=1,2,…,n-1

f(vivi+k)=4,i=1,2,…,n-k

情形2.2 當k≡0(mod 3)時，將頂點分段，每段中有k+1個頂點，即{v1,v2,…,vk+1}，{vk+2,vk+3,…,v2(k+1)}，…，每段中頂點如下染色：用1，2，3循環染色，最后一個頂點染色2，例如{v1,v2,…,vk+1}中的頂點v1,v2,…,vk用1，2，3循環染色，最后vk+1染色2。所有的邊均染色4。

綜上可知，

f(vi)=1,i≡1(mod 2)

f(vi)=2,i≡0(mod 2)

f(vivi+1)=1,i≡1(mod 2)

f(vivi+1)=2,i≡0(mod 2)

f(vivi+k)=3,i≡1(mod 2)

f(vivi+k)=4,i≡0(mod 2)

情形2.1 當k≡1,2(mod 3)時，

f(vi)=1,i≡1(mod 2)

f(vi)=2,i≡0(mod 2)

f(vivi+1)=1,i≡1(mod 2)

f(vivi+1)=2,i≡0(mod 2)

f(vivi+k)=3,i≡1(mod 2)

f(vivi+k)=4,i≡0(mod 2)

情形2.2 當k≡0(mod 3)時，將頂點分段，每段中有k+1個頂點，即{v1,v2,…,vk+1}，{vk+2,vk+3,…,v2(k+1)},…,每段中頂點如下染色：對其前k個頂點，用1，2，3循環染色，最后一個頂點染色2，例如{v1,v2,…,vk+1}中的頂點v1,v2,…,vk用1，2，3循環染色，最后vk+1染色2。

f(vivi+1)=1,i≡1(mod 2)

f(vivi+1)=2,i≡0(mod 2)

f(vivi+k)=3,i∈{tk+1,tk+2,…,tk+k}，t=0,1,2,…

f(vivi+k)=4,i∈{tk+k+1,tk+k+2,…,tk+2k}，t=0,1,2,…