路的D（3）-點可區別的全染色

張東翰，朱 白

(商洛學院 數學與計算機應用學院，陜西商洛 726000)

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

1 定義及引理

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

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

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

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

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

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

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

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

猜想1[9]對于階數不小于2的簡單連通圖G，有 χβνt(G)≤μβ(G)+1?！?br>