關(guān)于距離圖著色問(wèn)題的一點(diǎn)研究.pdf

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

2、c<,3>,……c<,k>},使: u,v∈V(G),u,v相鄰時(shí),有:f(u)≠f(v).圖G的點(diǎn)色數(shù)是χ(G)=min{k:V(G)→{c<,1>,c<,2>,c<,3>,……c<,k>}是圖G的正常著色},而圖的圓色數(shù)是其點(diǎn)色數(shù)的自然推廣,Vince以星色數(shù)引入這個(gè)概念.設(shè)p,q均為正整數(shù),且p≥2q,圖G=(V,E)的(p,q)-著色是指這樣一個(gè)映射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是從圖的獨(dú)立集族S到區(qū)間[0,1]的一個(gè)映射,使對(duì)任意點(diǎn)x,有:Σ<,x∈s,s∈S>c(s)≥1,而分式色數(shù)χ<,f>(G)≤χ<,c>(G)≤χ(G).當(dāng)|D|≤3時(shí),距離圖G(Z,D)的點(diǎn)色數(shù)、圓色數(shù)、分式色數(shù)幾乎都得到了圓滿 的解決.但是,當(dāng)|D|≥4這方面的結(jié)果還不多.另外,對(duì)于其他類型的