关于完备色数（II）

平面图Ｇ（Ｖ，Ｅ，Ｆ）的完备色数χｃ（Ｇ）是使得集合Ｖ（Ｇ）∪Ｅ（Ｇ）∪Ｆ（Ｇ）中的相邻点，相邻边、相邻面、相关联的点边、相关联的点面及相关联的边面均染为不同颜色的最少颜色数。一个无割点的外平面称为开外平面图。如果它的每一个内面的边界至少含一条外边。本文证明了：若Ｇ为开外平面图且其顶点最大度△（Ｇ）≥６，则χｃ（Ｃ）＝△（Ｇ）＋１。     

关于外平面图的完备着色

本文证明了对每一个△(G)≥3的外平面图G,有X~c(G)≤△(G)+3,其中X~c(G)为G的完备色数,△(G)为G的顶点最大度。     

立方Halin图的完备色数

 证明了每个立方Halin图H是完备6可着色的,并且H有一个完备6-着色,使得每一种色出现在每一个面(顶点)以及与其相邻(关联)的顶点、边和面的着色集中。     

外平面图的完备染色

设Ｖ（Ｇ）、Ｅ（Ｇ）和Ｆ（Ｇ）分别为平面图Ｇ的点集、边集和面集。Ｇ的完备色数Ｘｃ（Ｇ）是使得Ｖ（Ｇ）∪Ｅ（Ｇ）∪Ｆ（Ｇ）中相邻或相关联的元素间均染不同色的最少颜色数。本文证明了：对无割点的外平面图Ｇ，有Ｘｃ（Ｇ）≤ｍａｘ｛７，△（Ｇ）＋１｝，其中△（Ｇ）为Ｇ的最大度数。     

外平面图的松弛竞赛色数

主要研究外平面图的松驰竞赛色数。如果缺陷度d =2 ,3 ,4 ,k =7-d ,我们能够分别给Alice一个策略 ,使得对 (k ,d) 松弛染色竞赛Alice能赢。     

七色定理的一个新证明

平面图G的完备色数是使用G的相邻或相关联的元素均染为不同色的最少颜色数,Kronk和Mitchem证明了每一个最大度不超过3的平面图是7－完备可染的,本文利用四色定理给出定个定理的一个简单证明。     

外平面图的围长和分数色数

讨论了外平面图的围长和分数色数的关系 ,给出了分数色数的一个上界 ;对于固定的整数g ,给出了围长是g的外平面图的分数色数的上确界f0 (g) ,并得出若n为正整数 ,有f0 (2n) =f0 (2n +1) =2 +1 n成立 .     

一些特殊平面图的圆色数

给出了四类无穷族平面图的圆色数：第一族平面图的圆色数介于3和4之间;最后两族平面图的圆色数都是7/2;第二族平面图的圆色数为11/3,这是一族满足圆色数介于7/2和4之间的无穷族平面图,回答了Gao提出的问题．     

3-正则Halin图的完备染色

研究了3-正则(或立方)Halin图的完备染色,针对非轮图的3-正则Halin图,提出了一种具体的完备染色,简单确定了非轮图(W_n)的3-正则Halin图的完备色数是6,且使得3-正则Halin图的完备染色可用计算机实现。     

n个图的逻辑积的色数和边色数

证明了图的逻辑积的色数公式ｘ（Ｇ１∧Ｇ２∧…∧Ｇｎ）≤ｍｉｎ｛ｘ（Ｇ１），ｘ（Ｇ２），…，ｘ（Ｇｎ）｝，边色数有并作如下猜想：ｘ（Ｇ１∧Ｇ２∧…∧Ｇｎ）＝ｍｉｎ｛ｘ（Ｇ１），ｘ（Ｇ２），…，ｘ（Ｇｎ）｝．     

开外平面图的边面全色数

一个无割点的外平面图称为开外平面图，如果它的每一个内面的边界至少含有一条外边。本文证明了：若Ｇ为开外平面图，则（ｉ）当△（Ｇ）＝３时，ｘ２３（Ｇ）＝４，当△（Ｇ）≥５时，ｘ２３（Ｇ）＝△（Ｇ）；（ｉｉ）当△（Ｇ）＝２，４时，４≤ｘ２３（Ｇ）≤５，其中ｘ２３（Ｇ）为平面图Ｇ的边面全色数，△（Ｇ）是Ｇ的点最大度。     

若干n重积图的点可区别边色数

通过研究若干n重积图的边色数及点可区别边色数,就可证明■(Gi)=△(Gi),i=1,2,L,n,则∑=′×××=■△(G_i)其中G1×G2×L×Gn为G1,G2,L,Gn的n重积图.     

极大平面图的面色数

极大平面图 G的面色数不超过 4,且其为 4当且仅当G为 4阶完全图     

若干平方图的均匀全色数

讨论了路,圈,星,扇和轮的平方图的均匀全染色问题,得到了其均匀全色数.     

图的色数与着色数的上界

证明了对于围长不少于2k1的图G,其色数X(G)≤c((bk,2k+1+2)n)1/k+1+2,其中c=c(k)且limk→∞ c(k)=1,bt,k是G的booksize.另外还证明了对于围长不少于2k+1的图G,其着色数σ(G)≤[bk,2k+1+1)n/2]1/k+2.     

系列平行图的边色数

Vizing(1964年）和Gupta（1966年）各自独立地证明了边着色中的重要定理：对任何简单图G,表X′（G）＝△或X′（G）△＋1。但确定一个图G的边色数仍是一个尚未解决的问题。本文利用系列平行图的结构性质,确定了它的边色数。     

图的三类色数之间的一些关系

本文研究图与其补图的三类色数之间的关系,得到了满意的结果。     

几种特殊图形的分数色数研究

图的着色问题是图论中的一个重要研究课题之一,分数色数作为正常色数的一个推广在计算机的许多领域中有着重要的应用.本文研究了一些特殊图形的分数色数,给出了计算这些图形分数色数的公式,并且对公式进行了证明.