图的着色证明与图的着色定理——兼对四色猜想命题的证明

本文续接拙作《图的形成原理与图的模式及图的本质》的证明,依据图的面与面之间的关系和组合原理,指出四色猜想不属于＂真的机器证明之命题＂,而是属于三角数学范畴的命题;应用＂同中求异、异中求同＂的证明方法和数学建模方式,对五道雷同于四色猜想命题的命题进行了逐一证明,进而对＂为什么展现在不同物体表面的图其仅需用颜色区分的种数也不同的问题＂（包含＂为什么展现在平体表面的图仅需用4色就足以将其各面区分开的问题＂）作出证明。     

破解四色猜想命题的切入点在哪里

本文运用逻辑推理和抽丝剥茧的方法,围绕＂破解四色猜想命题的切入点在哪里＂这个问题,循着＂四色猜想命题的不可理解性的两个因素→排除图的需用颜色非决定性因素→图的面与面之间的关系及其理论依据＂的思路进行层层分析证明,最后得出了＂图的形成原理才是真正切入点＂的答案。     

图的仅需着色种数与其区分等式和其他问题——兼对地图四色区分的证明

本文续接《图的着色证明与图的着色定理》一文,着重于对＂地图以4色区分会不会发生‘爆炸’的问题＂和＂图的‘仅需着色种数’与其区分等式＂进行了证明,证明四色猜想成立。同时,应用＂两点连线＂的证明方法对事物中的连接现象进行了论证,强调＂组合与区分＂两者之间关系才是四色猜想命题研究的归结点。此外,指出物体表面的全相邻力是验证物体同胚体的依据,可构造出需用百、万、亿种颜色区分的整体。     

基于kn连接关系的图的着色问题与"折叠法"

引入了一类基于连接关系的图,并结合“折叠法”对该类图的着色问题与四色猜想进行了研究,给出了四色猜想的一个必要条件和一个等价命题的证明．最后提出了相关的猜想．     

色本原多项式的应用

组合计数和图的着色是组合数学与图论的重要内容,而Pólya计数定理和计算图色数的色多项式是研究它们的主要工具,在文献[3]中,杜清晏教授将两者结合,定义了色轨道多项式和色本原多项式,并提出了P-图和SC-图的概念。本文讨论了具体图Cn以及由图Cn组合的图的色轨道多项式和色本原多项式,还给出色轨道多项式和色本原多项式在化学上的应用。     

图的着色理论研究与发展

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

圈的推广Mycielski图的圆色数

Mycielski图是1955年由Mycielski提出来的．任给一个图G和一个非负整数m,G的推广Mycielski图μm(G)是G的Mycielski图的一个自然的推广．推广Mycielski图的性质以及它们的点色数、圆色数和分数色数等已有许多研究．本文研究圈的推广Mycielski图的圆色数．定义Cn为n个顶点的圈．对任意非负整数m和大于2的整数n,本文确定了图μm(Cn)的圆色数,同时还得到了图μm(Cn)-v的圆色数的一些结果．     

一些图的关联着色

1993年．Brualdi和Massey猜想每一个图G可以用△（G）＋2种色正常关联着色．尽管Algor和Alon通过一个例子否定了该猜想,但是对一些特殊图类该猜想可能成立．通过给出块图和单圈图的关联色数。证明了猜想对这两类图成立,并讨论了图G和H的冠图的关联色数．     

我对四色猜想命题的解读及证明方法的比较

本文透过事物现象,以独有的视角,对四色猜想命题的实质性问题,包括要解答的问题是什么、地图不等于平面图、"两个数字密码"、四色区分与分为四色的异同等问题进行了解读,同时,运用实例将本人的"组合说"证明方法与其他证明方法作比较,让人们在比较中作出鉴别.     

5色图包含子式K-5的一个简单证明

Hadwiger提出如下猜想:若G是k色图,则包含子式Kk,其中k=5时等价于四色定理.本文给出了5色图的一个必要条件,即5色图包含子式K-5.     

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

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

四色猜想命题中的第三种假象

本文以对图的相邻点点数和非相邻点点数是否产生影响、对图的需用颜色区分种数是否产生影响为检验依据,运用作图证明的方法,对＂面的编号是以全排列数出现在图的整体之中＂这一表面现象进行了论证,得出了它是假象的结论。     

论三角图的色多项式

本文引进了三角图的色分解的概念,给出了三角图的色分解系数与三角图色多项式根的重数之间的关系.     

单圈图及其与完全图联图的全染色

研究单圈Cn’,一类单圈图G以及它们与完全图Km联图Cn’∨Kn,G∨Kn的全染色问题.借助于已知的完全图全染色的相关引理以及归纳总结的方法得出了Cn’,G的全色数以及其与完全图联图Cn’∨Kn,G∨Kn的全色数,从而验证了对这类图全染色猜想的正确性.     

一类关联图的Star Extremal性质

证明了Cn的关联图I(Cn)是循环图,还证明了所有Cn的关联图I(Cn)及一些与I(Cn)有关的图是star extremal的.并用一种同构的方法得到了它们的圆色数和分色数.     

一致膨胀图和广义圈、广义轮图的分数色数

图的着色问题是图论的重要研究课题之一,分数色数作为正常色数的一个推广在计算机的许多领域中有着重要的应用.文章研究了一致膨胀图分数色数与原图分数色数之间的关系,并给出广义圈、广义轮图的分数色数.     

三类组合图的色等价性定理

目的 研究图的色等价性.方法 利用图的伴随多项式的因式分解式,分析图的色等价性.结果 从星图Sn+1,的三类组合图得到它们的伴随分解式和色等价图.结论 图的色等价性可通过研究其补图的伴随多项式的分解式得到.     

图P_n~k的着色

设k是一个正整数,在含有n个顶点的路Pn=v1v2…vn上,当且仅当两点的距离为k(k≥2)时增加一条边,这样所得到的图叫做Pnk(v1,vn),有时Pkn(v1,vn)也简记为Pnk.论文研究图Pnk的点着色、边着色和点、边全着色,得到图Pnk的点色数、边色数和图Pnk满足点、边全着色猜想等结论.     

图Pkn的着色

设k是一个正整数,在含有 n个顶点的路Pn=v1v2…vn上,当且仅当两点的距离为 k(k≥2)时增加一条边,这样所得到的图叫做Pkn(v1,vn),有时Pkn(v1,vn)也简记为Pkn.论文研究图Pkn的点着色、边着色和点、边全着色,得到图Pkn的点色数、边色数和图Pkn满足点、边全着色猜想等结论.     

I(Cn)的圆色数

讨论了n-圈Cn的关联图I(Cn)的结构性质.证明了I(Cn)是4-正则的平面图并研究了其色数.主要研究I(Cn)的圆色数并得到结果:如果n=3m,则χc(I(Cn))=χ(I(Cn))=3;如果n=3m 2,则χc(I(Cn))=(6m 4)/(2m 1).当n=3m 1时,给出了χc(I(C3m 1))的一个界.