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

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

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