關(guān)于路的k-方圖的鄰點(diǎn)可區(qū)別-邊全染色和第一類弱全染色

嚴(yán)謙泰

(安陽師范學(xué)院 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，河南 安陽 455000)

1 研究背景

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

V(Gk)=V(G)

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

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

2 主要結(jié)論

引理2[6]對(duì)任意的簡單圖G有

引理3[6]對(duì)于n階圈Cn有

引理4[7]對(duì)任意的簡單圖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 當(dāng)k≡1,2(mod 3)時(shí)，

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 當(dāng)k≡0(mod 3)時(shí)，將頂點(diǎn)分段，每段中有k+1個(gè)頂點(diǎn)，即{v1,v2,…,vk+1}，{vk+2,vk+3,…,v2(k+1)}，…，每段中頂點(diǎn)如下染色：用1，2，3循環(huán)染色，最后一個(gè)頂點(diǎn)染色2，例如{v1,v2,…,vk+1}中的頂點(diǎn)v1,v2,…,vk用1，2，3循環(huán)染色，最后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 當(dāng)k≡1,2(mod 3)時(shí)，

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 當(dāng)k≡0(mod 3)時(shí)，將頂點(diǎn)分段，每段中有k+1個(gè)頂點(diǎn)，即{v1,v2,…,vk+1}，{vk+2,vk+3,…,v2(k+1)},…,每段中頂點(diǎn)如下染色：對(duì)其前k個(gè)頂點(diǎn)，用1，2，3循環(huán)染色，最后一個(gè)頂點(diǎn)染色2，例如{v1,v2,…,vk+1}中的頂點(diǎn)v1,v2,…,vk用1，2，3循環(huán)染色，最后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,…