完全多部图和笛卡儿积图的线性点荫度

图的线性点荫度是对它的顶点进行染色所用的最少颜色数，同时使得染同一种颜色的点集所导出的子图，它的每个分支均为路．本文完全确定了完全多部图的线性点荫度，给出了笛卡儿积图的线性点荫度的一个上界，得到了一些特殊图（ 如路，圈和完全图） 的笛卡儿积图的线性点荫度．

关于图的线性点荫度

Ｂｒｏｅｒｅ和Ｍｙｎｈａｒｄｔ等人猜想：任何平面图Ｇ的线性点荫度ｌａ（Ｇ）不超过３。本文证明了这个猜想，并证明了外平面图的线性点荫度ｌａ（Ｇ）不大于２。

整数距离图G(D_(m,2))的点线性荫度

整数距离图G(D)以全体整数为顶点集 ,顶点u ,v相邻当且仅当 |u -v|∈D ,其中D是一个正整数集 .对于m 11,设Dm ,2 ={ 1,2 ,… ,m} \{ 2 } ,得到了G(Dm ,2 )的点线性荫度的上界和下界并决定出了它在某些特殊的m上的确切值 .

整数距离图G(D_(m,3))的点线性荫度

整数距离图G(D)以全体整数为顶点集,顶点u,v相邻当且仅当|u-v|∈D,其中D是一个正整数集.对于m>3,设Dm,3={1,2,…,m}\{3},本文得到了G(Dm,3)的点线性荫度的上界和下界并决定出了它在某些较小的m上的确切值.

整数距离图G(D_(m，k，2))的点线性荫度

整数距离图G(D)以全体整数作为顶点集,顶点u,v相邻当且仅当|u-v|∈D,其中D是一个正整数集．本文讨论整数距离图的点线性荫度,记为vla(G(D))．对于m≥5k,设D_(m,k,2)={1,2,…,m}/{k,2k),得到vla(G(D_(m,1,2)))=■并决定出了G(D_(m,2,2))在某些特殊的仇值上点线性荫度的确切值以及当k≥3时G(D_(m,k,2))的点线性荫度的上、下界．

Halin图的线性k-点荫度

图G的线性点荫度vla(G)是指V(G)的最小划分数,使得每个点划分集的导出子图为线性森林.G的线性k-点荫度vlak(G)是指V(G)的最小划分数,使得每个点划分集的导出子图的每个连通分支为长度至多为k的路.1998年,吴建良证明了Halin图的线性点荫度为2.本文在此基础上,证明了对Halin图G,有vlak(G)=2,其中k=max{[△-2/2],3}.

Halin图的一些路分解

本文证明了：若Ｇ是Ｈａｌｉｎ图，则Ｇ的线性荫度为［△（Ｇ）／２］，点荫度和线性点荫度为２，路分解数等于它的奇数度顶点的一半。