路的D（3）-點(diǎn)可區(qū)別的全染色

張東翰，朱 白

(商洛學(xué)院 數(shù)學(xué)與計(jì)算機(jī)應(yīng)用學(xué)院，陜西商洛 726000)

圖的染色是圖論中最著名和最古老的問題之一，由于其應(yīng)用的廣泛性使得越來越多的人對(duì)其進(jìn)行了研究,文獻(xiàn)[1-3]討論了圖的點(diǎn)可區(qū)別的邊染色，文獻(xiàn)[4]提出了圖的距離不大于β的任意兩點(diǎn)可區(qū)別的邊染色并對(duì)一些特殊圖的色數(shù)進(jìn)行了探討，文獻(xiàn)[5-7]對(duì)特殊圖的2，3，4距離的染色做了一些研究，文獻(xiàn)[8]對(duì)特殊圖的全染色進(jìn)行了研究，文獻(xiàn)[9]提出了圖的距離不大于β的點(diǎn)可區(qū)別的全染色并對(duì)一些特殊圖的色數(shù)進(jìn)行了探討,文獻(xiàn)[10]研究了蛛形圖的D（3）-點(diǎn)可區(qū)別的全染色。圖的距離染色是圖染色研究的熱點(diǎn)之一，并已經(jīng)取得了很多重要的結(jié)果。通過對(duì)大量文獻(xiàn)的研讀，研究了路的距離不大于3的點(diǎn)可區(qū)別的全染色。

1 定義及引理

定義1[8-9]設(shè)G(V，E)是簡(jiǎn)單圖，k是正整數(shù)，f是從 V(G)∪E(G)到 C={1，2，…，k}的映射，如果滿足：

1）對(duì)任意的邊 uν∈E(G)，f(u)≠f(ν)f(u)≠f(uν)≠f(ν)；

2）對(duì)任意的兩相鄰的邊uν,uw∈E(G)(ν≠w),f(uν)≠f(νw)；則稱 f是圖 G 的一個(gè)正常全染色(簡(jiǎn)記作 k-PTC)，且稱數(shù)為G的全色數(shù)。

如果f是一個(gè)k正常全染色，并且滿足：

3）對(duì)任意的 u,ν∈V(G)，u≠ν,dG(u,ν)≤β,其中dG(u,ν)表示u與ν的距離，β是正整數(shù)，有C(u)≠C(ν)，也就是

顯然，當(dāng)β=1時(shí)，D(1)-點(diǎn)可區(qū)別的全染色是鄰點(diǎn)可區(qū)別的全染色，當(dāng) β=diam(G)時(shí)，D(β)-點(diǎn)可區(qū)別的全染色是點(diǎn)可區(qū)別的全染色，其中diam(G)表示圖 G 的直徑，且分別用 χat(G)和 χνt(G)表示χ1νt(G)χdνt(G)，其中 d=diam(G)。

引理1[9]設(shè)G是連通圖且，則有，χβνt≥μβ(G),其中稱為圖G的組合度，ni表示使任意兩點(diǎn)間的距離不超過β的度為i的點(diǎn)的最大數(shù)目，δ和△分別表示圖G的最小度和最大度，θ是正整數(shù)。

引理2[9]設(shè)G是連通圖且，那么有χat(G)≤χβνt(G)≤χdνt(G)。

猜想1[9]對(duì)于階數(shù)不小于2的簡(jiǎn)單連通圖G，有 χβνt(G)≤μβ(G)+1。

2 定理及其證明

定理1 設(shè)Pn是n(n≥4)階的路，則有 χνt(Pn)=4。

證明：當(dāng)n≥4時(shí)，μ3（Pn）=4，根據(jù)引理1可知χ3νt（Pn）≥4，要證明χ3νt（Pn）=4成立，只需給出一個(gè) 4-D（3）-VDTC，設(shè)色集合 C={1，2，3，4}，Pn=ν1ν2·…·νn-1νn，現(xiàn)給出一個(gè) 4-D（3）-VDTC，對(duì)于邊ν1ν2,ν2ν3,…,νn-1νn分別用色 3，4，1，2 循環(huán)染；對(duì)于點(diǎn) ν1，ν2，…，νn分別用色 1，2，3，4 循環(huán)染，則此染色法是一個(gè)正常的全染色，又因?yàn)楫?dāng)2≤i≤n-1且i≡0(mod4)時(shí)（νi）={3}；2≤i≤n-1且i≡1(mod4)時(shí)（νi）={4}；當(dāng)2≤i≤n-1且i≡2(mod4)時(shí)，（νi）={1}；當(dāng)2≤i≤n-1且i≡3(mod4)時(shí)，C（νi）={2}；當(dāng)n=4時(shí)（νi）={2,4}（ν4）={2,3}，當(dāng)n≥5時(shí)，dG（νi,νn）≥4,由此可知，對(duì)于距離不大于 3 的任意兩點(diǎn)色集合不同，所以此染色法為一個(gè)4-D(3)-VDTC，因此定理成立。

[1]BalisterP N,HuangY Q,Chu YM.Vertexdistinguishng edge colorings of graphs[J].J of Graph Theory,2003,42:95-109.

[2]Bazgan C,Harat—Benhamdie A,Li H,et al.On the vertex-distinguishng edge colorings of graphs[J].J of Combin Theory,1999,75:288-301.

[3]Burris A C,Schelp R H.Vertex-distinguishng proper edge colorings[J].J of Graph Theory,1977,26:73-82.

[4]張忠輔,李敬文,陳祥恩,等.圖的距離不大于β的任意兩點(diǎn)可區(qū)別的邊染色[J].數(shù)學(xué)學(xué)報(bào):中文版,2006,49(3):703-708.

[5]于蘭蘭.單圈圖的距離色數(shù)[J].甘肅科學(xué)學(xué)報(bào),2009,21(3):41-42.

[6]陳海鈺,劉信生.最大度為△圖類的距離色數(shù)的一個(gè)下界[J].甘肅科學(xué)學(xué)報(bào),2007,19(3):4-5.

[7]田京京.路和圈的距離不大于3和4的點(diǎn)可區(qū)別的邊染色[J].蘭州理工大學(xué)學(xué)報(bào),2008,34(4):156-158.

[8]張東翰.路的廣義Mycielski圖的全染色[J].商洛學(xué)院學(xué)報(bào),2012,26(2):9-10.

[9]張忠輔,李敬文,陳祥恩,等.圖的距離不大于β的點(diǎn)可區(qū)別的全染色[J].中國科學(xué):A輯,2006,36(10):1119-1130.

[10]張東翰.蛛形圖的D(3)-點(diǎn)可區(qū)別的全染色[J].海南大學(xué)學(xué)報(bào)：自然科學(xué)版,2013,31(4):300-302.