Heawood反例图的全部四着色

本文首次报告了Heawood反例图的全部四着色.它可以用一个树林来描述.树林的每个分支是一棵四着色树.四着色树是一个根树.根节点Cr是Heawood反例图的一个四着色.根树其它节点都是经过一个或多个二色变换从Cr变来的.Heawood反例图有37个四着色树.其中有35个偶四色树(包括24个是仅有根结点的退化型四色树),2个奇四色树.偶四着色总计112,奇四着色总计144,全部四着色总共256个.这些结果都是用Maple编程得到的.     

平图的四着色与对偶图的H圈

阐明了平图中的H圈与对偶图顶点四着色的依存关系.提出了平图的顶点四着色和对偶图顶点四着色的具体步骤.介绍了多面体平图的H圈分解与对偶图顶点四着色,以及对偶图的H圈分解与平图的顶点四着色.讨论了平图及对偶图的H圈的个数,森林Fi的个数及顶点四着色方案数.     

基于平图的H圈分解的对偶图的四着色

阐明了平图中的H圈与对偶图中的森林Fi及顶点四着色的依存关系,提出了一种基于H圈分解的任意平图的顶点四着色方法。介绍了20面体平图中的90个H圈及对偶图中的90个森林Fi及90种顶点四着色方案。讨论了平图及对偶图中的H圈Ci的个数,森林Fi的个数和顶点的四着色方案数。     

平面三次图哈米尔顿性的一个充要条件

本文证明平面三次图Dg有哈米尔顿圈的充分必要条件是与之对偶的极大平面图g有树树型四着色．即Dg的对偶极大平面图g有四着色C，该四着色的某组对偶二色子图Gk的两个分支都是树．据此得到求出图Dg全部哈米尔顿圈的算法，该方法已经成功处理了批量例图．     

全部四着色解的基着色+自同构群表示法

本文在文献[1]的基础上，利用同构四着色类和基着色的概念，给出了用基着色和自同构群表达描述全部四着色解的一种方法。这种方法密切联系着图的对称性，可大大节省存储空间。     

图的着色理论研究与发展

文章主要介绍了图的着色理论的发展史,分析了＂四色猜想＂在着色理论中的特殊地位;最后,对近年来新出现的一些重要着色问题做了简要的探讨。     

平面三次图中的二元哈米顿圈

本文定义了平面三次图中的二元哈米顿圈,并证明了:平面三次图Dg有二元哈米顿圈,充分必要的是,与之对偶的极大平面图g有树-圈-树型四着色,更具体地说是,与图Dg对偶的极大平面图g有四着色C,该四着色的某组对偶二色子图:Gk=RUS,其中R连通并且仅仅包含一个圈;S有两个分支,并且都是树.据此,得到求出图Dg全部二元哈米顿圈的算法.该方法已经成功处理了批量例图.     

平图中的H圈与对偶图的顶点4着色

阐明了平图的4着色及对偶树与对偶图中的H图的依存关系,以及对偶图的4着色及对偶树与平图中的H圈的依存关系。给出了平面H圈和对偶图顶点4着色的基本思路,得到了对偶图与三角剖分图之间的关系,并利用此关系提出了平图及对偶图的H圈及对偶树的分解方法和顶点4着色方法。这两种方法都是通过给出对偶图成平面的面中心的H圈得到对偶树,并对对偶树进行着色而得到的。介绍了46面体平图及对偶图中的H圈及对偶树的各种分解方案和顶点4着色方案。结果表明:任意平图中的H圈必定将对偶图分解为两棵对偶树,且两棵对偶树的2着色等价于对偶图的顶点4着色,从而使kempe四色猜想"证明"中的错误得以纠正。     

极大平面图的导出四正则图的三着色

本文给出了极大平面图的导出四正则图的两种构造方式、等价性及性质,证明了导出四正则图的三着色与原极大平面图四着色的一一对应关系,并且找出了导出四正则图的三种颜色与原极大平面图四着色的三组对偶二色子图之间的关系.     

中国建筑师问题与对偶问题的4着色

提出了中国建筑师问题,阐明了求解中国建筑师问题的基本思路。介绍了25个顶点、69个边、45个面的对偶图的顶点4着色的全过程。将对偶图分解成含2棵可以2着色的对偶树的森林,在以r、b两色为对偶树得到的顶点实施2着色,以y、g两色为对偶树得到的顶点实施2着色,从而实施对偶图顶点的4着色。阐述了对偶图的4着色关键是将对偶图分解出森林,提出了3个森林的分解方法,讨论了H路径的个数、森林的个数、对偶图的A区和B区划分方案、对偶图的顶点4着色方案数。解决了对偶图顶点的4着色问题,利用对偶图顶点4着色方法使Kempe四色猜想"证明"中的漏洞得到了弥补。将此种方法用于12面体、20面体、22面体、32面体的对偶图的4色问题,并取得了成功。     

用面扩树的方法找三次图的边三着色

本文通过分析三次图中面的奇偶性及组合情况,引出了可边三色块的概念,接着用面扩树方式给出了三次图中大量的可边三色块,在这些可边三色块中导出了三次图的一些边三色解.     

关于图色常量N（（3,3）,5）的结果

N((3, 3), 5) denotes the minimum N so that there exists a graph of N vertices which doesn't contain complete subgraph on 5 vertices and can't be (3, 3)-colored. It is shown that N ((3, 3), 5) = l5.     

连通图划分定理及其在图计数中的应用

本文证明了关于连通图划分的一个定理.运用这个定理,简化了标号连通图和标号树的递归计数关系的证明,并导出了给定价数和根点块数的有根标号连通图和二色标号连通图的递归计数式.     

关于图P6k+43∪Pn3的优美性

讨论了形如P63k+4∪Pn3非连通并图的优美性,用构造性的方法给出了P36k+4∪Pn3的优美标号,并证明P63k+4∪Pn3是交错图.     

关于图的Ramsey数的几个下界

推广了3个C4对完全图的R am sey数下界以及一个经典R am sey数下界问题,得到了3个C4对完全图的R am sey数的线性下界,以及一个关于多项式的经典R am sey数下界.     

关于图的4-色数

本文研究了图的４色数的界，得到了完全图．完全ｍ－部图、轮、圈和树的４－色数及图与补图４－色数间的关系，证明了图Ｇ与补图Ｇ的４－色数之和介于ｐ＋１与２ｐ之间。     

图的一类新双变量色多项式

根据Klaus Dohmen等提出的图的新双变量色多项式概念,探究了一般图关于此定义的减边公式,利用它反复迭代后可以方便地求得任何图的新双变量色多项式,还利用它深入探讨了一些特殊图的新双变量色多项式公式.同时还探究了运用包含等偏序关系,利用M(o)bius反演法和“格子剖分”法求得图的新双变量色多项式.最后探讨了共点图的新双变量色多项式公式以及图的顶点和边与色多项式的关系.     

图∪ni=1Fmi,4的优美性

给出图∪ⁿ_i=1F_{mi,4的一类非连通图, 并证明这类图是优美图, 且也是交错图.}     

关于S_m∨K_(n,n)的全色数

图染色是实际问题的重要数学模型,也是图论的研究内容之一.文章通过一类联图的全色数的确定,得到了阶星Sm和完全等二部图Kn,n联图的全色数.     

强正则图的补图的能量

设G是一个n阶简单连通图,G的能量定义为G的特征值的绝对值之和．对于强正则图的能量研究,已有许多学者得到了一系列深刻的结果．本文研究具有参数（n,r,u,v）的强正则图G的补图G^-的能量问题,我们得到了一个不等式：2（n-r-1）≤E（G^-）≤（n-r-1）＋n/2／n-1.