关于图的顶点划分数

该文讨论了无爪图的顶点划分数,给出了完全n部图的顶点划分数的计算公式,最后证明了任意图的点线荫度不大于它的边线荫度且不等式是精确的.     

乘积图的荫度

研究了乘积图的荫度并对一般的图G ,H ,给出了其乘积图G×H 荫度上界 .对一些特殊图类的乘积图 ,给出了其荫度的显性表达式     

Halin图的一些路分解

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

图的点线荫度

图G的顶点集V(G)划分为一些子集,使得每个子集的导出子图是0线森林(即每个分支是路)的最小子集数叫图G的点线荫度,记为v|a(G).Poh K S证明了任何平面图的点线荫度最多是3.Matsumato M给出了图的点线荫度的上界,即v|a(G)≤[△(G)/2].这里△(G)是G的最大度.本文给出了完全n部图的点线荫度计算公式,同时也给出了任意图的点线荫度的精确上下界．     

图和补图的荫度

本文研究了图和补图荫度间的关系,并猜想:对p阶简单图G(V,E),有 a(G)+a(G~c)≤1+[p/2] 其中G~c表示G的补图,a(G)表示G的荫度,[x]表示不小于x的最小整数。     

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

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

无指定相交圈的非负特征图的列表点荫度

对于图的任一顶点集的划分,并使每个划分的导出子图均为无圈图的最小的划分基数称为图的顶点荫度.对于图G的每个顶点给定一个列表基数至少为k的颜色集合,对于图的任一染色,若每个顶点的颜色均选择与其关联的颜色集,使得每种颜色类的导出子图是一个无圈图的最小的基数k称为图的列表点荫度.证明了每个无6圈和相交i,j-圈(i,j∈{3,4})的非负特征图的列表顶点荫度为2,即为4列表可选色.     

图的控制数与点线荫度的关系

该文给出了图的控制数与2倍点线荫度之和及积的上界且所给出的界均可达到。     

图的全色数强色数和点荫度

利用图标的方法得到图的全色数的一个上界，并证明其是可达的。其次给出图的强色数的一个上界，并对极图予以刻划，最后对图与补图的点荫度之间的关系给出一个简单的证明。     

Halin图的线性2-荫度

图G的线性2荫度la2(G)是将G分解为k个边不交的森林的最小整数k,其中每个森林的分支树的长度至多为2的路.给出了Halin图G的线性2荫度.     

线图的荫度

文中讨论了线图的荫度,得到了线图荫度的若干界。对于完全图及树,确定了其线图荫度的精确值。     

荫度与全独立数全覆盖数的关系

研究了图的荫度、边荫度与其余独立数、全覆盖数间的关系，得到了不可改进的结果。     

均衡完全三部图K3（n）的线性3-荫度

考虑均衡完全三部图K3（n）的线性3-荫度.利用路分解的方法给出了K3（n）的线性3-荫度la3（Κ3（n））当n≡1,2,3（mod 4）时的比较紧的上界,利用线性k-荫度的基本理论分别得到了它们的下界,进而得到了特殊情况下均衡完全三部图K3（n）的线性3-荫度的确切值.     

外平面图的平方图的点荫度

图G的平方图G2是以V(G)作为它的点集，两个点在G2中相邻当且仅当它们在G中的距离至多为2.证明了：若G是一个最大度Δ6的外平面图,则G2的点荫度va(G2)=「Δ+12?;特别地，一棵树T的平方图T2的点荫度va(T2)=「Δ+12?.     

上可嵌入图与次上可嵌入图的线性荫度

通过度再分配的方法研究上可嵌入图与次上可嵌入图的线性荫度,证明了最大度△不小于(4-3ε)~(1/3)且欧拉示性数ε≤0的上可嵌入图其线性荫度为「△/2」.对于次上可嵌入图,如果最大度△≥(4-3ε)~(1/3)且ε≤0,则其线性荫度为「△/2」.改进了文献[1]中最大度的的界.作为应用证明了双环面上的三角剖分图的线性荫度.     

平面图线性2-荫度的一个上界

设图G为最大度为Δ的平面图。图G的线性2-荫度是将图G的边集合分解成k个线性森林的最小整数k,其中每个分支树为长至多为2的路,记为la2（G）。得到了平面图线性2-荫度的上界：若Δ≡0,3（mod 4）,则la2（G）≤「Δ/2棢＋8;若Δ≡1,2（mod 4）,则la2（G）≤「Δ/2棢＋7。     

较大亏格曲面嵌入图的线性荫度

通过度再分配的方法研究嵌入到曲面上图的线性荫度.给定较大亏格曲面∑上嵌入图G,如果最大度Δ(G)≥((45-45ε)^(1/2)+10)且不含4-圈,则其线性荫度为[Δ/2],其中若∑是亏格为h(h>1)的可定向曲面时ε=2-2h,若∑是亏格为k(k>2)的不可定向曲面时ε=2-k.改进了吴建良的结果,作为应用证明了边数较少图的线形荫度.     

边数较少的图的线性荫度

设G是一个连通图且满足|E|≤|V| [3△／2]-4,则它的线性荫度la(G)=[△／2],同时得到了一个与树相关的结果。     

有限图的边荫度分解

设有限图Ｇ＝（Ｖ，Ｅ），Ｐ＝｛Ｖ１，Ｖ２，…，Ｖｒ｝为Ｇ的一个划分，收缩Ｖｉ为一点ｖｉ（ｉ＝１，…，ｒ），得到Ｇ的收缩图ＧＰ＝（ＶＰ，ＥＰ）．文中通过对Ｇ递归地进行收缩，改进了Ｇ的边不重生成树数目的上界，并给出了Ｇ的边荫度分解的具体方法     

某些不含5-圈的图的线性2-荫度

线性森林是所有分支都为路的图,图G的线性荫度la(G)也就是把图的边集分解为互不相交的线性森林的最少数量k.本文对将要讨论的不含5-圈的平面图做一些限制,这些图不含3-面与3-面相邻、4-面与4-面共用一条边的情况.设G为不含5-圈的如上述所示的平面图,则la2(G)≤(Δ(G)+1/2)+5.