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

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

关于匹配数为1的极大2-均衡3-部3-图的结构

描述具有给定匹配数的极大k-一致超图的结构是一个尚未解决的问题.本研究充分利用完全2-均衡3-部3-图中所有互不相交的完美匹配,得到极图的边数,进而确定所有极图的结构.     

平面图线性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。     

特殊平面图的线性二荫度

线性k-森林是指一个图G,它的每个连通分支是长至多为k的路．图G的线性k-荫度是指使得G可以边划分成m个线性k-森林的最小整数m,用lak（G）表示．本文探讨特殊平面图的线性二荫度,得到的结论有：1）每个3-圈不重边的平面图G,有la2（G）≤[△（G）／2]＋10;2）每个3-圈不重点的平面图G,有la2（G）≤[△（G）／2]＋7;3）每点至多关联[△（G）／2]个3-面的平面图G,有la2（G）≤[△（G）／2]＋10．     

不含4-圈和5-圈的平面图的线性2-荫度

线性k-森林是每一个连通分支均为长度不超过k的路的图。一个图G的线性k-荫度是将图G的边集合能分解成的线性k-森林的最少数目,用lak(G)来表示。证明了:若G为不含4-圈和5-圈的平面图,则la2(G)≤「Δ(G)+1/2■+4。     

唯一3-列表可染图Kr,s,t和K1*r,s的若干性质

2001年Ghebleh M和Mahmoodian E S针对完全多部图这一重要图类（除了其中9个图）,特征化了U3LC图。同时他们对这9个图提出了开放问题：查证图K（2,2,r）,r=4,5,6,7,8,K（2,3,4）.K（1＊4,4）,K（1＊4,5）和K（1＊5,4）不是U3LC图。鉴于此开放问题中待查证的图或是完全三部图K（r,s,t）或是完全多部图K（1＊r,s）,笔者从反面入手研究U3LC完全三部图K（r,s,t）和完全多部图K（1＊r,s）的性质,以期实现最终利用这些性质彻底解决如上开放问题,完善Ghebleh M和Mahmoodian E S的结果。     

完全二部图的K_(1,4)-因子分解(英文)

讨论了完全二部图的因子分解 ,并给出了 4 Km,n存在 K1,4 -因子分解的充分条件 .     

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

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

图的点线荫度

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

Halin图的一些路分解

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

完全三部图K(n- k,n,n)的色性

设Ｐ（Ｇ,λ）表示简单图Ｇ的色多项式;若对任意简单图Ｈ 满足Ｐ（Ｈ,λ） ＝ Ｐ（Ｇ,λ）,都有Ｈ 与Ｇ同构,则称Ｇ是色唯一图;设Ｋ（ｍ ,ｎ,ｒ） 表示完全三部图;本文证明了：（１） 若ｎ ＞ ｋ ＋ ｋ２／３,则图Ｋ（ｎ － ｋ,ｎ,ｎ） 是色唯一的,（２） 若ｎ ≥８,则Ｋ（ｎ － ４,ｎ,ｎ） 是色唯一的;     

关于完全三部图K(n-k,n,n+k)的色性

设Ｇ为简单图,Ｐ（Ｇ,λ）的色多项式,若对任意简单图Ｈ满足Ｐ（Ｈ,λ）＝Ｐ（Ｇ,λ）,都有Ｈ与Ｇ同构,则称Ｇ是色唯一图,设Ｋ（ｍ,ｎ,ｒ）表示完全三部图,证明了：（１）对任意非负整数ｋ,若ｎ≥２√－３ｋ／３＋ｋ＾２,则Ｋ（ｎ－ｋ,ｎ,ｎ＋ｋ）是色唯一图。（２）若ｎ≥９,则Ｋ（ｎ－３,ｎ,ｎ＋３）是色唯一图。     

完全三部图K（n,n,n＋k）的色性

设Ｇ为简单图,Ｐ（Ｇ,λ）为Ｇ的色多项式。若对任意简单图Ｈ满足Ｐ（Ｈ,λ）＝Ｐ（Ｇ,λ）,都有Ｈ与Ｇ同构,则称Ｇ是色唯一图,设Ｋ（ｍ,ｎ,ｒ）表示完全三部图。证明了（１）对任意非负整数ｋ,若ｎ≥ｋ＋ｋ＾２／３,则Ｋ（ｎ,ｎ,ｎ＋ｋ）是色唯;（２）若ｎ≥４,则Ｋ（ｎ,ｎ,ｎ＋４）是色唯一图。     

完全三部图K（m,n,r）的色唯一性的进一步结果

设G是简单图,用P（G,λ）表示图G的色多项式,若对任意简单图H使P（H,λ）,都有H与G 同构,则称G是色唯一图,令K（m,n,r)表示完全三部图。     

Halin图的线性2-荫度

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

不含相交4-圈的平面图的线性2-荫度

设G是不含相交4-圈的平面图.证明了若G是连通图且最小度δ(G)≥2,则G包含一条边xy使得d(x)+d(y)≤9或一个2-交错圈.由这一结果得到G的线性2-荫度la_2(G)≤「Δ/2┐+6.     

完全二部图的少面数强嵌入

通过调整完全二部图G的少双圈覆盖中的某些圈，可得到一个强嵌入，没的双圈覆盖可以得到不同的强嵌入，最后作为推论，得到完全三部图Kn,n,n可以强嵌入到某一亏格的曲面上。     

完全三部图K2,2,r,r=4,5,6,7,不是U3LC图

M.Ghebleh和E.S.Mahmoodian在其开放问题中提出了完全三部图K2,2,r,r=4,5,6,7,是U3LC图还是具有M(3)性质这样一个问题。在这篇文章中我们叙述并证明了图K2,2,7具有M(3)性质这样一个主定理,进一步证明了图K2,2,r,r=4,5,6,也具有M(3)性质。     

4-圈不共点的平面图的线性2-荫度

图G的线性2-荫度la₂(G)是指可以使G分解为k个边不相交森林的最小整数k, 其中森林的每个分支是长度至多为2的路。 证明了若G是4-圈不共点的平面图,则la₂(G)≤「Δ/2+5。