n阶完全图全着色的构造及其推广

引进了图的全着色矩阵的概念,从而给出了n阶完全图全着色的构造,并推广到任意n阶图G的最大度Δ(G)=n-1的情形,给出了与猜想等价的命题·     

完全二部图全着色的构造

利用全着色矩阵给出完全二部图全着色的构造,该构造可以方便快捷对完全二部图进行全着色.     

全着色的一个定理

本文证明了着正则图全着色猜想成立,则全着色猜想成立.     

图与其子图全色数的关系

研究了图与其子图全色数的关系，并且证明了全着色猜想对某些特殊图形成立．     

乘积图G×Pn和G×Cm的全着色

本文证明对乘积图G×Pn和G×Cm,若G∈C1T,则G×Pn∈C1T,G×C2m∈C1T和G×Cm∈C1TC2T;从而证明了乘积图Pr1×Pr2...×Pm∈C1r,Cr1×Cr2...×Cm∈C1T∪C2T.由此证明了对于这些图全着色猜想成立.     

区间图和强弦图的全着色及最优算法

证明对于任意区间图和强弦图－全着色猜想成立，并且给出了区间图和强弦图的最优线性地，其算法复杂度仅为Ｏ（Ｖ＋Ｅ）。     

n拟偶图的全色数

引入ｎ拟偶图，对ｎ≤３时当ｎ〉３时，剖分边集导出子图为道路，圈、Ｋ１３的细分图或Ｋ１．３＋ｅ的细分图等情形证明了全着色猜想。     

几类含圈图的全着色

对于图G=（V，E），一个正常全着色就是从VUE到一个整数集的映射，使VUE中的任意两个相邻或相关联的元素都着不同的颜色，图G=（V，E）的全色数xτ（G）定义为xT（G）=min{k｜存在G的一个正常k-全着急}，本文对一类特殊图-含圈图的全着色给出了几个定理，验证了全着色猜想。     

几个特殊图的全着色

设G是一个图,G的全着色是一个映射π:V(G)YE(G)C,使得相关联或相邻的元素着不同色;G的所有全着色中,使得色数的最小者,称为G的全色数,记为χT(G);得到了几个特殊图的全色数     

关于强边着色猜想的最优图问题

著名图论专家Erd(o)s和Ne(s)et(r)il对图的强边着色数上界提出了一个猜想:当△为偶数时,x's(G)≤5/4△2;当△为奇数时,x's(G)≤1/4(5△2-2△+1),他们给出了当△=4的时的最优图.此处构造了一族图,并以此证明了当△为偶数时,如果Erd(o)s和Ne(s)et(r)il提出的强边着色猜想成立,则猜想中的上界是最优的.     

2－退化图的全色数

对任意简单图Ｇ，Δ（Ｇ）和ＸＴ（Ｇ）分别表示Ｇ的最大度和全色数．证明了当Δ（Ｇ）≥４时，２－退化图Ｇ的全色数ＸＴ（Ｇ）＝Δ（Ｇ）＋１．     

两类联的全色数

图G的全色数χT(G)是使得V(G)∪E(G)中相邻或相关联的元素均染不同颜色的最少数目.如果χT(G)=Δ(G)+1,则称G是1-型的.证明了在m≠n1+2时非等部完全偶图Kn1,n2(n1相似文献   

图的D(b)-点强可区别的全染色

提出了图的D(b)-点强可区别的全染色的概念并给出了几个基本定理,通过穷举法和组合分析法研究了b=2时,路图的具体染色,最后提出了一个猜想.     

完全多部图满足全色数猜想的一种新的证明方法

Ｂｅｈｚａｄ〔１〕和Ｖｉｚｉｎｇ〔２〕独立提出了全色数精想：对任意图Ｇ，有ｘＴ（Ｇ）≤Δ（Ｇ）＋２。本文的主要结果如下：（１）用一种新的方法证明了完全多部图满足全色猜想（２）证明了点数不大于１０的图满足全色数猜想。     

完全图正常△+2全着色的构造

本文直接给出完全图的一种正常Δ+2全着色。