四度图的异构类快速算法(Ⅰ):A型域与简单B型域的情形

根据四度图G（4）的顶点数δ(i)的偏导数规律，得到快速写出G（4）的全是构类的算法。解决了A型域和简单的B型域的情形。     

涉及距离的n-因子-临界图的一个充分条件

证明了如下结论：设G是p阶连通图，其中p≡n（mod2）且n＜p，如果对满足条件d（u,v）＝2的任意点集{u,v}包含于V（G），有d(u) d(v)≥p n-1，则G是n－因子－临界图。     

围长至少为5的平面图的线性着色

本文研究了围长至少为5的平面图的线性着色问题。利用反证法,通过分析最小反例图的结构,运用欧拉公式结合适当的权转移规则得出矛盾,从而证明了围长至少为5的平面图的线性色数满足lc(G)≤[△(G)/2]+4,改进了这方面的结果。     

k-连通半无爪图的Hamilton性质

半无爪图是包含无爪图的更大的图类。关于k-连通半无爪图,得到以下结果:G是k-连通的半无爪图(k≥2),如果对于G2的任意基数为k 1的独立集X,都有∑d(v)≥n-k,则G是Hamilton图。     

Halin图和Series-Parallel图的动态色数

图的动态着色是Bruce Montgomery于2001年引入的一个新概念。本文分别证明了Halin图和非5圈的Series—Parallel图的动态色数都不超过4。     

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

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

关于混合图的特征向量的结构

设G为一个混和图.它是通过对一个无向图定向其中的某些边而获得.若G为简单图,关于G的对应次小特征值的特征向量的结构,Fiedler给出一个值得注意的结论.当G为恰含一个非奇异圈的混合图时,关于G的对应最小特征值的特征向量的结构,根据Fiedler的结论,获得一个类似结果.     

一个K1,3-free图猜想

1988年在美国的Kalamazoo召开的“第六届国际图论及其应用会议”上提出无爪图猜想：若3连通;n≥3阶K1,3-free图G的NC≥(2n-6)／3,则G是哈密尔顿图。证明此猜想,并指出此猜想可能不是最好,但用此方法可有利于进一步得到更好的结果。     

关于临界的圆色数的一个注记

圆色数是正常着色的一个推广,由Vince在1988年首次提出．现我们考虑这样一个问题：对于Vε〉0,是否存在一个具有高连通性的临界图G使得Xc（G）≤X（G）-1＋ε？对此,Steffen和Zhu已证明对Vm≥4存在满足要求的m-连通（m＋1）-临界图,只留下一种情形未解决,即G的连通度为3时的情形．在这篇文章中我们就此情形进行讨论,并给出肯定结论．     

一类1-边可删的导出匹配可扩图的刻画

设图G是有2n个顶点的简单图,如果删去G的任意k条边后得到的图是导出匹配可扩的,则称G是k-边可删的导出匹配可扩图.给出了4-正则、不包含K1,4作为导出子图、1-边可删的导出匹配可扩图的完全刻画.