最大度至多为3的图上极大分离集的最大数目

给定图G=（V,E）,若顶点子集F在图G中的导出子图的最大度至多为1,则称F为图G的一个分离集;若F不是其他分离集的真子集,则称F为一个极大分离集。对极大分离集计数问题进行研究,证明了在所有n个顶点且最大度至多为3的图上最多有\begin{document}${6^{\frac{\mathit{n}}{{\rm{4}}}}}$\end{document}个极大分离集,并刻画了相应的极图结构。     

邻集并与最大度的Hamilton性质

通过讨论无爪图的Hamilton性质,在给出邻集并与最大度的条件下,Hamilton图的一个充分条件 在某些意义下,这个条件是最好的可能     

枚举图的全部极大独立集的普遍性方法

完整地研究了寻找一个图的全部极大独立集所需要的理论、寻找范围、计算公式和枚举方法，采用有根树描述，以邻接矩阵中任意一行所对应的顶点为根，再以该行中各个非零元素所对应的那些顶点为根，按照文中所述方法生成有根树，这些有根树就描述出图的全部极大独立集，本方法已用计算机程序实现。     

用神经网络研究图的最大独立集问题

利用人工神经网络的原理．将图的最大独立集问题转换为人工神经网络的问题．对此网络进行了分析．并用计算机进行模拟．给出了不同规模的图的优化解．     

生成图的全部极大独立集的一般方法

图的极大独立集问题是图论中重要的NPC问题,独立集具有广泛的应用领域,如编码理论、信道分配、资源配置、纠错码理论等.文章运用拟序关系理论,系统研究了生成图的全部极大独立集的一般方法,该方法简单实用,程序化实现容易.     

基于图着色的极大团求解算法

极大团问题是图论中一个经典的组合优化问题,也是一类NP完全问题,在国际上已有广泛的研究。作者在对其他现有极大团求解算法进行研究之后,设计了一种基于图着色思想的极大团求解算法。基本思想是通过不同的方式对随机图的相应补图进行顶点着色,寻找出所有顶点的极大独立集。而后返回到原图之中找出极大团,并且通过比较删减寻找到随机图的所有极大团。     

单圈图的最大拉普拉斯分离度

设G为一个简单图,记μ_1(G)和μ_2(G)分别为G的拉普拉斯最大特征值和次大特征值,G的拉普拉斯分离度定义为该图的拉普拉斯矩阵的最大特征值与次大特征值之差。本文研究了给定阶数的单圈图的最大拉普拉斯分离度,并刻画了相应的极图。     

分类集及极大分类集的计数

Ｍ是（１，２，…，ｎ）的一些子集合的集合。若Ｍ中任意两个子集，或者它们无共同元素，或者一个是另一个的子集，这样的Ｍ称为分类集。若不存在（１，２，…，ｎ）的一个分类集包含Ｍ，称Ｍ为极大分类集。给出分类集及极大分类集个数ｔｎ及Ｔｎ的计算，并由Ｔｎ的两个递推关系式得到一些组合恒等式。     

用神经网络新方法求解图的最大独立集问题

在Ｈｏｐｆｉｅｌｄ神经网络优化方法的基础上,根据模拟退炎算法逃离局部最优解的原理,提出了一种神经网络计算的新方法,并用这种方法求解图的最大独立集问题。结果表明,该方法获得最优解比Ｈｏｐｆｉｅｌｄ神经网络优化算法获得的解要好,且所需时间比模拟退火算法少得多。     

最大度为6的平面图是13-线性可染的

图G的线性色数lc（G）是指G的所有线性染色中所用的最少颜色的个数．运用Discharging方法,研究了平面图的线性色数问题,证明了最大度为6的平面图是13-线性可染的．     

关于最大度为 7 的平面图全染色的一个注记

给最大度为Δ的图进行全染色至少要用Δ+1种颜色.全染色猜想断言每个图都是(Δ+2)-全可染的.但即使对于平面图,全染色猜想依然未得到证实.在该研究方向已证明满足下述条件之一的最大度为Δ的平面图是(Δ+1)-全可染的:1)Δ≥9;2)Δ=8且不含相邻三角形.证明了最大度为7且不含带弦4-圈和带弦5-圈的平面图是8-全可染的.该结果进一步拓展了(Δ+1)-全可染平面图类.     

最大度是5的可平面图的边染色

对于最大度是Δ的可平面图G,如果χ′(G)=Δ,称G为第一类图;如果χ′(G)=Δ+1,称G为第二类图.χ′(G)表示G的边染色数.1965年,Vizing举例说明Δ=5的可平面图中既有第一类图,也有第二类图.作者运用Discharge方法证明最大度是5且不包含有弦的4-圈和有弦的5-圈,或不包含有弦的4-圈和有弦的6-圈的可平面图是第一类图.     

最大度为6且不含4-圈和7-圈的平面图的边列表和全列表

令G是一个最大度为△(G)的平面图.运用Dischanging方法,进一步探究△(G)≥6的平面图的边列表色数,得到了最大度为6且不含4-圈和7-圈的平面图的边列表色数为△,全列表色数为△+1.     

最大度为4的外平面图的无圈边色数

一个图G的无圈边染色是一个正常的边染色,使得任一个圈上至少有3种不同的颜色.G的无圈边色数a＇（G）是使得G有无圈k-边染色的最小整数k.设G是一个最大度为4的外平面图.对于现有结果 4≤a＇（G）≤5中,何时为4,何时为5,还没有一个完整的刻画.给出一个使得a＇（G）=4的充分条件,拓展了该领域的相关结果.     

关于高度极大外平面图的4染色

从最大度的角度讨论两大极大外平面图的公共４染色，证明了当Ｇ是以ｒ个顶点的圈Ｑｒ为标定界环的极大外平面图且△（Ｇ）≥ｒ－２，Ｇ′是以Ｑｒ为标定界环的任一极大外平面图时，Ｇ和Ｇ′有公共４染色，从而证明了四色定理的等价例题在给定条件下成立。     

最大度顶点互不相邻的高度图的全色数

研究了最大度顶点互不相邻的高度图的全色数．得到：设图Ｇ的最大度顶点是互不相邻的，且δ（Ｇ）≥３４｜Ｖ（Ｇ）｜，则ｘＴ（Ｇ）＝Δ（Ｇ）＋１     

最大度等于5的图的强边色数

最大度等于5的图的强边色数至多为38.     

高度平面图的L(p,q)—标号

研究高度平面图G的L(p,q)-标号问题，证明了高度平面图h1-图的L(p,q)-标号数满足:λ(G;p,q)(2q-1)Δ+6(p-q)；h2-图的L(p,q)-标号数满足:λ(G;p,q)(2q-1)Δ+8p-6q-1. 对于L(2,1)标号问题Griggs和Yeh有一著名猜想：对最大度为Δ的任意图有λ(G)Δ2. 此猜想对高度平面图是正确的.