關于距離圖著色問題的一點研究.pdf

1、一般說來,圖的著色問題最早起源于著名的"四色問題",染色問題不但有著重要的理論價值,而且,它和很多實際問題有著密切聯(lián)系,例如通訊系統(tǒng)的頻道分配問題,更有著廣泛的應用背景.距離圖是一類重要的無限簡單圖,設Z是全體整數(shù)集,D是一個正整數(shù)集,距離圖G(Z,D)是這樣的一類圖:點集是Z,x,y相鄰,若|x-y|∈D.它的染色問題和很多實際問題有著密切的關系.所謂圖G的正常點著色是指這樣一個映射f:V(G)→G<,k>={c<,1>,c<,2>,

2、c<,3>,……c<,k>},使: u,v∈V(G),u,v相鄰時,有:f(u)≠f(v).圖G的點色數(shù)是χ(G)=min{k:V(G)→{c<,1>,c<,2>,c<,3>,……c<,k>}是圖G的正常著色},而圖的圓色數(shù)是其點色數(shù)的自然推廣,Vince以星色數(shù)引入這個概念.設p,q均為正整數(shù),且p≥2q,圖G=(V,E)的(p,q)-著色是指這樣一個映射c:V→{0,1,2,……p-1},使 xy∈E,‖c(x)-c(y)‖<,p>

3、≥q,其中‖a‖<,p>=min{q,p-a}.圓色數(shù)χ<,c>(G)=inf{p/q:存在圖G的一種(p,q)-著色}.而圖G的分式著色c是從圖的獨立集族S到區(qū)間[0,1]的一個映射,使對任意點x,有:Σ<,x∈s,s∈S>c(s)≥1,而分式色數(shù)χ<,f>(G)≤χ<,c>(G)≤χ(G).當|D|≤3時,距離圖G(Z,D)的點色數(shù)、圓色數(shù)、分式色數(shù)幾乎都得到了圓滿 的解決.但是,當|D|≥4這方面的結果還不多.另外,對于其他類型的