所有的仙人掌图为1类图

根据仙人掌图的各种结构,证明了所有的仙人掌图对全染色猜想是成立的,并进一步证明了所有△（G）≥3的仙人掌图是1类的。     

C.Thomassen猜想的证明

证明了若G是3连通无爪图，且G的每个同构于A的导出子图都满足φ（α1，α2），则G是泛连通图（除了u,v∈V（G），d(u,v)=1时，G中可能不存在（u,v)-k路外）。由此立得C.Thomassen猜想：每个4个连通线图均是Hamilton图。     

关于3-圈不重点的平面图全染色的一个结论

给定一个图G，G的全k可染色是指至多用k种颜色，对G的顶点和边同时进行染色，使得相邻的或相关联的两个元素（点和边）不染同一颜色。图G的全染色数xτ（G）是指使G全k染色的最小整数k。△（G）是G的最大度，显然任何一个图不会是全△可染的，但是Vizing猜测任何一个图一定是全△＋2可染的。而这个全染色猜想，对平面图也仍是没有得到解决的。本文利用欧拉公式和重新分配的方法，对3-圈不重点的平面图进行了讨论，得出结论：最大度△≥8的任何两个3-圈不重点的平面图一定是全△＋1可染的。     

导出子图中不含K4-e的无爪立方图的完美匹配个数

设G是一个简单图,具有顶点集合V（G）和边集合E（G）。若图G的任意导出子图都不与K1,3同构,则称G是一个无爪图。一个立方图是一个所有顶点都是三度点的图。本文给出了一类特殊图--不含K4-e的无爪立方图的完美匹配计数。 更多还原     

Sm∨Fn的全色数

设G（V,E）是阶数至少是2的简单连通图,k是正整数,若厂是从V（G）∪E（G）到{1,2,…,k}的一个映射,使得：对于任意的uv,vw∈E（G）,u≠w,有f（uv）≠f（vw）;且对于任意的uv∈E（G）,u≠v,有f（u）≠f（v）,f（u）≠f（uv）,f（v）≠f（uv）,则称f为G的一个k-全染色（简记成k-TC of G）．而Xt（G）=min{k｜k—TC of G},称为G的全色数．设G和H是点边都不相交的简单图,V（G∨H）=V（G）∪V（H）,E（G∨H）=E（G）∪E（H）∪{uv｜u∈V（G）,v∈V（H）},则称G∨H是G与H的联图。给出m＋1阶星和n＋1阶扇的联图的全色数。     

关于最小度至少为3的图的全控制数

设G是一个没有孤立点的简单图.G的顶点集的一个子集S是一个全控制集,如果G的每个顶点都相邻于S中的某个顶点.图G的全控制数,用γt(G)来表示,是G的全控制集中的顶点数最少的全控制集的顶点数.证明了如果G是一个最小度至少为3的图,那么γt(G)≤n/2.从而证明了Favaron, Henning, Mynhart和Puech提出的一个猜想成立.     

关于3-圈不重点的平面图全染色的一个结论

给定一个图G,G的全k可染色是指至多用k种颜色,对G的顶点和边同时进行染色,使得相邻的或相关联的两个元素(点和边)不染同一颜色。图G的全染色数xT(G)是指使G全k染色的最小整数k。Δ(G)是G的最大度,显然任何一个图不会是全Δ可染的,但是Vizing猜测任何一个图一定是全Δ 2可染的。而这个全染色猜想,对平面图也仍是没有得到解决的。本文利用欧拉公式和重新分配的方法,对3-圈不重点的平面图进行了讨论,得出结论:最大度Δ≥8的任何两个3-圈不重点的平面图一定是全Δ 1可染的。     

闭包是完全图的无爪图的泛圈性

本文的主要结论：G是无爪连通图,M（G）={x｜x∈V（G）,x局部连通}是G的一个控制集,〈M（G）〉有两个分支,设为M1,M2,c1（G）是完全图时,G是泛圈的。     

一类图的△+2全着色

对一类特殊的图G(V,E),其中△(G)=v—1,v是G的顶点数,△(G)表示G的最大度,证明了全着色猜想成立。     

圈的距离不大于5的任意两点可区别的全染色

所谓图的D（β）-点可区别全染色是指图G的一个正常全染色且使得距离不大于β的任意2点有不同的色集合.文献[2]讨论了图的距离等于2和3的点可区别全染色,文献[3]讨论了图的距离等于4的点可区别全染色.本文主要讨论了圈的D（5）-点可区别的全染色.     

四色问题的探讨

基于最新有关平面图着色的成果[1～ 5 ] ,首先分析了关于四色猜想 A. B. Kempe证明的错误原因 ,并提出了纠正错误的方法 ,最后提出了四色猜想新证明.     

高度不正则图的全着色

图G的正常k全着色是指用k种颜色对G的点和边着色,使相邻或相关联的元素(点或边)着不同色。其中最小的k称为G的全色数,记为χT(G)。设G是一个简单图,υ是G的任意一个顶点,若与υ相邻的顶点的度互不相同,则称G为高度不正则图。对高度不正则图G,文中证明了χT(G)=Δ(G)+1,同时也给出了着色的算法,其中Δ(G)为G的最大度数且Δ(G)≥ 2。     

贪心消着色数与Grundy数

主要讨论贪心着色与Ｇｒｕｎｄｙ数的关系。证明了求Ｇｒｕｎｄｙ数问题是个ＮＰ－ｈａｒｄ问题，引入并了随意可着色图的概念及其相关性质，并证明识别随意可着产是个ＮＰ－ｈａｒｄ问题。     

考虑用户QoS的基于图论的干扰协调方案

为了提高小区边缘用户的性能,提出了一种基于图论的考虑用户业务质量（QoS）的干扰协调方案. 把无线资源分配问题映射成图论中的着色问题,同时考虑不同用户分到不同数量资源的场景,即一个点会需要不仅一种颜色的情况,引入了用户资源分配方式,并利用增强SEQ（sequential）着色算法解决该问题.仿真结果表明,提出的方案在不降低小区平均吞吐量的同时,能有效提升边缘用户的性能.     

实用化计算机辅助课表编排系统的研究与实现

大学课表的编排是一项复杂的工作，文章对大学学期课表的编排要求进行了全面的分析，给出了一个新的学期课表编排问题的排课表算法，该算法使用了图着色技术，讨论了一个实用的计算机辅助排课表系统的设计与实现。     

图中点对偶的几个着色定理及算法

探讨了简单图Ｇ＝（Ｎ，Ｅ）中不邻接点的着色问题，给出连通的简单图中，点对偶在ｒ（Ｇ）＝ｋ）着色中为同色和异色的性质，色数的存在区间等，提出了求简单图色数的一种较有效的算法。     

图的边重构性的一个注记

如果图Ｇ的每个边重构图都与图Ｇ同构,则称图Ｇ是边可重构的,图的边重构猜想是指所有的至少有４条边的有限无向简单图都是边可重构的,它是至今尚未解决的著名的图论问题之一,文章主要通过定义特殊函数的方法来研究图的边重构性问题,并给出仅以图的最大顶点次数和最小顶点次数作为参数的简单充分条件。     

地图的着色及着色算法

本文对地图着色的问题进行了一定的分析和讨论,并提出了地图着色的一个新算法,并将此算法和一些其它算法作了比较,说明了该算法的着色优点.     

"四色猜想"研究

“四色猜想”提出至今将近１５０年,百年来它吸引了众多数学家们。１９７６年美国数学家Ａｐｐｅｌ和Ｈａｋｅｎ宣布：他们用电子计算机花了１２００多小时证明了“四色猜想”是成立的。但人们仍期待着一个简单的理论证明,况且说后来有人指出了计算机证明的一些漏洞。