陳海鈺

(蘭州職業(yè)技術(shù)學(xué)院 經(jīng)濟(jì)管理系， 甘肅 蘭州 730000)

1．引言

約定：本文主要研究的樹(shù)T是除了懸掛點(diǎn)之外每一個(gè)點(diǎn)的度都達(dá)到最大度Δ(≥3)(因?yàn)樽畲蠖葹棣さ臉?shù)都是該樹(shù)的子樹(shù)),且d(T)≥k(d(T)表示T的直徑，如果d(T)

對(duì)圖G(V,E),令:

2. 主要結(jié)果

定理1設(shè)T是最大度為Δ的樹(shù)，且滿(mǎn)足上述約定，則

(其中l(wèi)=0,1,2,…).

證明:

當(dāng)k=2l時(shí),存在v∈V(T)使得|Bl[v]|=p,所以χk(T)≥p.為證明χk(T)≤p,下面用貪婪算法給出T的用了p種顏色的k-距離染色c:

當(dāng)k=2l+1時(shí),存在u0,u1∈V(T)使得|Bl[u0]∪Bl[u1]|=q,顯然,?u,v∈Bl[u0]∪Bl[u1],有d(u,v)≤2l+1.所以χk(T)≥q.為證明χk(T)≤q,下面用貪婪算法給出T的用了q種顏色的k-距離染色c:

圖中的v0 與

綜上，此染色方案可以使樹(shù)T有q種色的k-距離染色.

推論1[6]T是樹(shù),則χ(T)=2.

證明：定理1中取k=1即得結(jié)論.

推論2[7]若T是最大度為Δ的樹(shù),則χ2(T)=Δ+1.

證明：定理1中取k=2即得結(jié)論.