一种构造k-色临界图的方法

图G的色数Х（G）是指对图G进行着色并使相邻顶点具有不同颜色的最少颜色数,若对G的任意真子图H有Х（H）〈Х（G）=k,则称G是k-色临界的,因此可以给出一种构造k-色临界图的方法。     

几个特殊图类的路色数

研究了图的路色数,给出了补为路线或路的并的图的路色数及补为mK2或mK3的图的路色数。     

一种构造k—色临界图的方法

图G的色数χ(G)是指对图G进行着色并使相邻顶点具有不同颜色的最少颜色数,若对G的任意真子图H有χ(H)<χ(G)=k,则称G是k—色临界的,因此可以给出一种构造k—色临界图的方法。     

临界边共色图的构造

通过利用相关知识构造出两类临界边共色图,并利用无三角形图和线图的临界关系得到两类临界共色图。     

关于3—γ—临界图的Hamilton性

设ａｐ＾→ｂ是无终点的３－γ－临界图Ｇ的一条Ｈａｍｉｌｔｏｎｉａｎ路,文〔３〕证明了当ｄ（ａ,ｂ）＝３时,Ｇ是Ｈａｍｉｌｔｏｎｉａｎ图。本文进一步研究３－γ－临界图的Ｈａｍｉｌｔｏｎ性,得到如下结果：如果ｄ（ａ,ｂ）＝２且│Ｔ│＝１或Ｔ＝Ｎ＾－（ａ）∩Ｎ＾＋（ｂ）,则Ｇ是Ｈａｍｉｌｔｏｎｉａｎ图。这里,Ｔ＝Ｖ（Ｇ）－〔Ｎ（ａ）∪Ｎ（ｂ）∪｛ａ,ｂ｝〕。     

关于直径为2-临界图的Murty-Simon猜想

称图G是直径为2-临界图,如果G的直径是2,任意删掉一条边这个图的直径都会增加.一个非常著名的猜想,称为Murty-Simon猜想,指出对于任意有n个点的直径为2-临界图,它的边数最多为[n2/4」,且为完全二部图K[n/2],[n/2]时可以取到边数的上界.一个图称为是3t-临界图,简记为3tEC,如果它的全控制数是...     

荫度临界图的构造法

给出了由较小的荫度临界图构造较大的荫度临界图的一种合成的方法.     

一类k可扩图和一类n因子临界图

k可扩图和n因子临界图是近年来图论研究的热点。在本文中介绍了我们发现的新的k可扩图和n因子临界图。我们证明了一个对称设计的关联图是k可扩图。而Harary图则是n因子临界图。     

图与其补图路色数的关系

研究了图与其补图路色数的关系     

关于临界n_连通图的一些性质

本文给出了临界n_连通图的充要条件,临界n_连通图是第一类图和临界n_连通图(v<2n+1)是临界n_边连通图等性质.     

两种特殊冠图的相关分数色数研究

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

几类特殊图的圆色数性质

圆色数是图的色数概念的推广 .与色数相比 ,圆色数包含了更多有关图本身结构的信息 ,因而更加难以确定 .本文推导了 2类特殊图———图Ctk 和图Ctk-v的圆色数 ;并给出了图Hm ,n圆色数的一个简单证明 .     

一类距离图的圆色数

圆色数是图的一个重要参数 .距离图G(Z ,D)是具有顶点集Z ={ 0 ,± 1,± 2 ,… }、距离集D ,且满足顶点x与y相邻的充要条件是y -x∈D的无限图 .本文确定了两类距离图G(Z ,Dm ,k ,k + 1)和G(Z ,Dm ,k ,k + 1.k + 2 )的圆色数 .     

具有最小上色数的bi-超图的最小边数

若一个混合超图H=χX,C,Dχ满足C=D,则称H为bi-超图.本文主要讨论上色数最小的bi-超图的最小边数问题,证明了上色数为2的3一致bi-超图的最小边数为[n(n-2)/3],其中n为对应bi-超图的顶点数.     

具有唯一最大度点的Halin图的全色数

本文证明了：对于具有唯一最大度点的Halin图G，有G∈1/T={G|xT（G）=△（G） 1}。这是xT(G)表示图G的全色数，△（G)表示图G的最大度数。     

两类联图的边色数

两个不交图G与H的联G+H是指顶点集为V(G)∪V(H),边集为E(G)∪E(H)∪{xy|x∈V(G),y∈V(H)}的图.证明了当n=m+1时,联图Om+Cn是第二类图,否则,Om+Cn是第一类图;当|n-m|=1时,联图Cm+Cn是第二类图,否则,Cm+Cn是第一类图.