關(guān)于整數(shù)距離圖的點(diǎn)蔭度的若干問(wèn)題的研究.pdf

1、一個(gè)圖的к-著色是從圖的頂點(diǎn)集V(G)到集合{1，2，…，к}的一個(gè)映射。給定一個(gè)к-著色，令V<,i>為G中所有著色為i的頂點(diǎn)集，G[V<,i>]表示由V<,i>導(dǎo)出的子圖。若對(duì)每個(gè)1≤i≤к，V<,i>為獨(dú)立集，則，是一個(gè)正常к-著色。若圖G有一個(gè)正常к-著色，則稱G是к-可著色的。圖G的色數(shù)，記為x(G)，是使圖G為к-可著色的最小整數(shù)к。若x(G)=к，則稱G是к-色圖。若V<,i>導(dǎo)出的子圖的連通分支均為樹(shù)，則稱f是樹(shù)к-可著

2、色的。圖G的點(diǎn)蔭度，記為υα(G)，是使圖G有一個(gè)樹(shù)к-著色的最小數(shù)к。 給定正實(shí)數(shù)集的一個(gè)子集D，G(R，D)表示實(shí)數(shù)軸冗上一個(gè)圖，其頂點(diǎn)為R上所有點(diǎn)，并滿足兩個(gè)頂點(diǎn)x，y相鄰當(dāng)且僅當(dāng)｜x-y｜∈D。這樣的圖稱為距離圖，而集合D稱為該圖的距離集。若D為正整數(shù)集，則圖G(R，D)是由全體整數(shù)集Z導(dǎo)出的子圖，稱為整數(shù)距離圖，并記為G(D)。 在[56]中，我們對(duì)他們的證明進(jìn)行了整理，作出了一些改進(jìn)，得到了另一種形式的證明。