图的点染色理论一直是图论界的一个热门话题。一个图G的一个k-着色是从V（G）到{1,2,…,k}的一个映射,对于图G的一个给定的k-着色,Vi表示G中染i色的所有顶点,而G[Vi]表示Vi在G中的点导出子图。若Vi（1≤i≤k）都是独立集,则称f是一个正常k-着色。使得图G有正常k-着色的最小数k称为G的点色数,记为x（G）。若有x（G）=k,则称G是k-色图。若对于G的任意真子图H,都有x（H）i]（1≤i≤k）的每个连通分支都是树,则称f是一个树k-着色。使得图G有树k-着色的最小正整数k称为G的点荫度,记为va（G）。
Kronk等人证明了对于任意图G,有va（G）≤[(△（G）+1)/2]。Catlin等人证明了非圈非完全的图G的点荫度va（G）≤[(△（G）)/2]。（?）krekovski证明了局部平面图的点荫度≤3,而无三角形的局部平面图的点荫度≤2。***等人证明了任意平面图的点荫度≤3,以及n-部完全图K（p1,p2,…,p_n）(1≤p1≤p2≤…≤p_n)的点荫度是n-max{k|sum from 0 to k pi≤n-k},其中p0=0。后来有许多人,如***等,也研究了图的点荫度。
若G[Vi]（1≤i≤k）的每个连通分支都是路,则称f是一个路k-着色。使得图G有路k-着色的最小正整数k称为G的点线性荫度,记为vla（G）。显然,对于任意的图G,有va（G）≤vla（G）≤x（G）。
Matsumoto证明了:对于有限图G,vla（G）≤[(△（G）+1)/2],进而,若△（G）为偶数,则vla（G）=[(△（G）+1)/2]当且仅当G为△（G）+1阶的完全图或为一个圈;Goddard和Poh证明了对于平面图G,有vla（G）≤3;Akiyama证明了对于外平面图G,有vla（G）≤2。Alavi等人证明了对于任意阶为n的图G,有vla（G）+vla(（?）)≤1+[（n+1）/2],其中（?）是G的补图。
给定任一正实数集D,令G（R,D）表示实数轴上的所有点作为点集合,而两个
暂无评论