蛛形圖的D(3)-點可區(qū)別的全染色

張東翰

(商洛學院數(shù)學與計算科學系，陜西商洛726000)

圖的染色是圖論中最著名和最古老的問題之一，由于其應用的廣泛性使得越來越多的學者對其進行了研究.文獻［1-3］討論了圖的點可區(qū)別的邊染色，文獻［4］提出了圖的距離不大于β的任意2點可區(qū)別的邊染色并對一些特殊圖的色數(shù)進行了探討，文獻［5］對特殊圖的3，4距離的邊染色做了一些研究，文獻［6-7］對圖的2距離點色數(shù)給予了討論，文獻［8-9］對特殊圖的全染色進行了研究，文獻［10］提出了圖的距離不大于β的點可區(qū)別的全染色并對一些特殊圖的色數(shù)進行了探討，對蛛形圖的色數(shù)的研究有一定的實際意義，文獻［11］討論了蛛形圖的若干染色問題.圖的距離染色是圖染色研究的熱點之一，并已經(jīng)取得了很多重要的結果.筆者利用構造具體染色的方法，確定了蛛形圖的距離不大于3的任意2點可區(qū)別的全色數(shù).

1 預備知識

定義1［10］設 G(V，E)是簡單圖，k 是正整數(shù)，f是從 V(G)∪E(G)到 C={1，2，…，k}的映射，若

1)對任意的邊 uvE(G)，有 f(u)≠f(v)，f(v)≠f(uv)≠f(v)，

2)對任意的2條相鄰的邊uv，uw E(G)(v≠w)，有f(uv)≠f(uw)，則稱f是圖G的一個k-正常全染色(簡記作k-PTC)，且稱數(shù)χT(G)=min{k|圖G存在k-PTC}為G的全色數(shù).

設β為正整數(shù)，f是圖G的一個k-正常全染色，對任意的x V(G)，讓C(x)表示在f下點x的顏色以及與x關聯(lián)的邊的顏色構成的集合，稱之為點x在f下的色集合.C(x)在全體k種顏色構成的集合中的補集記為(x)，若對任意的u，vV(G)，且u 與v在G 中的距離dG(u，v)≤β，u≠v都有C(u)≠C(v)，那么稱f為圖G的一個k-D(β)-點可區(qū)別全染色(簡記為k-D(β)-VDTC)，并將χβ-vt(G)=min{k|G有一個k-D(β)-VDTC}稱為圖G的D(β)點可區(qū)別全色數(shù).

定義2［11］蛛形圖Sk的頭點為v0，從v0出發(fā)有k(k≥3)條路，每條路的長為k，共有n(n=k2+1)個點，刪去v0后，得到的彼此不交的k條路分別記為Pi=vi1vi2…vik，(1≤i≤k)，eij表示Pi中連接vi(j-1)和vij(1≤i≤k，2≤j≤k)的邊，連接 v0和 vi1的邊記為 ei1(1≤i≤k).

引理1［10］設 G 是連通圖且|V(G)|≥3，則有(G)，其中ni表示使任意2點間的距離不超過β的度為i的點的最大數(shù)目，δ和Δ分別表示圖G的最小度和最大度，θ是正整數(shù).

本文中未加述及的術語、記號可參考文獻［12-13］.

2 定理及其證明

定理1 設Sk是蛛形圖，則有χ3-vt(Sk)=k+1.

證明 當k=3時，μ3=4，根據(jù)引理1可知χ3-vt(Sk)≥4，要證明χ3-vt(Sk)=4成立，只需給出一個4-D(3)-VDTC. 現(xiàn)給出一個4-D(3)-VDTC，使用的顏色為 1，2，3，4. 對于邊 v0v11，v11v12，v12v13分別用色 1，3，4染;對于邊 v0v21，v21v22，v22v23分別用色 2，4，1 染;對于邊 v0v31，v31v32，v32v33分別用色 3，4，1 染，對于點 v0用色 4 染，對于點 v11，v12，v13分別用色 2，1，2 染;對于點 v21，v22，v23分別用色 1，3，2 染;對于點 v31，v32，v33分別用色2，3，2染，則此染色是一個正常的全染色，又因為

可知對于距離不大于3的任意2點色集合不同，所以此染色為S3一個4-D(3)-VDTC，因此當k=3時結論成立.

當k≥4時，μ3=k+1，根據(jù)引理1可知 χ3-vt(Sk)≥k+1，為了證明 χ3-vt(Sk)=k+1，只需給出一個Sk-(k+1)-D(3)-VDTC，使用的顏色為 1，2，…，k+1，對于邊 v0v11，v11v12，…，v1(k-1)v1k分別用色 1，2，3，4，5，…，k 染;對于邊 v0vi1，vi1vi2，…，vi(k-1)vik分別用色 i，i+1，…，k，1，2，…，i-1 染 i=2，3，…，k;對于點 v0用色k+1 染;對于點 v11，v12，…，v1(k-1)，v1k分別用色 3，k+1，2，3，…，k-1 染;對于點 v21，v22，…，v2(k-1)，v2k分別用色 4，k+1，3，…，k 染;對于點 v(k-1)1，v(k-1)2，…，v(k-1)(k-1)，v(k-1)k分別用色 1，k+1，k，1，2，…，k-3 染;對于點 vk1，vk2，…，vk(k-1)，vkk分別用色 2，k+1，1，2，…，k-2 染;對于點 vi1，vi2，…，vi(k-1)，vik分別用色 i+2，k+1，i+1，i+2，…，k，1，2，…，i-2 來染 i=3，4，…，k-2，則此染色法為 Sk一個正常的全染色，又因為

且每條路Pi=vi1，vi2，…，vik，(1≤i≤k)上各個邊都染不同的顏色，所以在正常全染色下每條路上的任意2點的色集合不同.因此對于距離不大于3的任意2點其色集合不同，所以此染色為一個(k+1)-D(3)-VDTC.當k≥4時結論成立.

綜上所述，定理1成立.

［1］BALISTER P N，HUANG Y Q，CHU Y M.Vertex-distinguishng 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-distinguishing proper edge-colorings of graphs［J］.J.of Combin Theory，1999，75:288-301.

［3］BURRIS A C ，SCHELP R H.Vertex-distinguishing proper edge colorings［J］.J.of Graph Theory，1977，26:73-82.

［4］張忠輔，李敬文，陳祥恩，等.圖的距離不大于β的任意兩點可區(qū)別的邊染色［J］.數(shù)學學報，2006，49(3):703-708.

［5］田京京.路和圈的距離不大于3和4的點可區(qū)別的邊染色［J］.蘭州理工大學學報，2008，34(4):156-158.

［6］于蘭蘭.單圈圖的2距離色數(shù)［J］.甘肅科學學報，2009，21(3):41-42.

［7］陳海鈺，劉信生.最大度為Δ圖類的2距離色數(shù)的一個下界［J］.甘肅科學學報，2007，19(3):4-5.

［8］張東翰.路的廣義Mycielski圖的全染色［J］.商洛學院學報，2012，26(2):9-10.

［9］楊鵬輝.輪形圖的全著色［J］.海南大學學報:自然科學版，2011，29(1):8-10.

［10］張忠輔，李敬文，陳祥恩，等.圖的距離不大于β的點可區(qū)別的全染色［J］.中國科學:A輯，2006，36(10):1119-1130.

［11］孫亮萍，強會英，孟利冬.蛛形圖的若干染色問題［J］.蘭州交通大學學報，2011，30(4):41-42.

［12］BONDY J A，MURTY U S R.Graph Theory with Applications［M］.New York:Elsevier Science Publishing Co.，1976.

［13］REINHARD D.Graph Theory［M］.New York:Springer-Verlag，1997.