子立方图的2-距离严格邻点可区别边染色

2-距离严格邻点可区别边染色是指图G有一个正常边染色,且任意2个距离为2的顶点的颜色集合互不包含.2-距离严格邻点可区别边色数是指使图G有一个2-距离严格邻点可区别边染色的最小颜色数值,记作χ′_(2-snd)(G).采用反证法证明了:若图G是子立方图,则χ′_(2-snd)(G)≤7.

子立方图的严格邻点可区别全染色

图G的一个正常k-全染色是指一个映射,使得中任意两个相邻的或相关联的元素染不同颜色。令Cφ(v)表示点v的颜色与v的关联边的颜色组成的集合。如果满足对任意一条边都有和,则称φ是k-严格邻点可区别的。图G的严格邻点可区别全色数是使G是k-严格邻点可区别全可染的最小正整数k,用χsnt(G)表示。本文证明了每个子立方图满足。

混合超图的染色理论

混合超图是含有两种超边的超图,一种称为D-超边,一种称为C-超边,它们的区别主要体现在染色要求上.混合超图的染色,要求每一D-超边至少有两个点染不同的颜色,每一C-超边至少有两个点染相同的颜色.用颜色最多的染色所用的颜色数称为该混合超图的上色数,用颜色最少的染色所用的颜色数称为该混合超图的下色数.混合超图的染色理论是目前国际组合学界比较新的研究课题之一.本文主要概括介绍关于混合超图染色理论已经取得的一些成果,其中包含本文作者的研究成果.并提出了一些可供进一步研究的问题.

具有最小连通点对图的C-超图的染色讨论

主要讨论C-超图的染色与点的点对图的连通性之间的关系,证明了对任意给定的不小于3的正整数n,都存在上色数为n且具有最小连通点对图的3一致C-超图.

C-超图的最小边数与染色问题

讨论了3一致C＿超图的最小边数问题,给出了上色数为2的3一致C＿超图的最小边数的一个上界.

平面图的严格邻点可区别染色

图G的严格邻点可区别边染色是一个正常边染色,使得每对相邻顶点所关联的边的颜色集合互不包含.G的严格邻点可区别边色数χ’snd(G)是使G有一个严格邻点可区别k-边染色的最小整数k.本领域存在一个重要猜想:除去一个特殊图HΔ外,每个没有叶子的简单图G都满足χ’snd(G)≤2Δ.当前最好的已知上界是χ’snd(G)≤3Δ-1.一个自然而有趣的问题是,哪类没有叶子的图满足χ’snd(G)≤Δ+C,其中C是一个不依赖于最大度Δ的常数?本文部分地回答了这个问题,即证明了对围长至少为5的平面图G,有χ’snd(G)≤Δ+25.这里围长大于等于5的条件不能被减弱到小于等于4的情形.

3一致C-超图的最小边数

混合超图是含有两类超边的超图,一类称为C-超边,一类称为D-超边,它们的区别主要体现在染色要求上．混合超图的染色,要求每一C-超边至少有两个点染相同的颜色,而每一D-超边至少有两个点染不同的颜色．所用的最大颜色数称为对应混合超图的上色数,所用的最小颜色数称为对应混合超图的下色数．上、下色数与边数有密切关系．作者在文献[2]中证明了具有最小上色数的3一致C-超图边数的一个下界为‘n(n-2)/3’,其中n为对应混合超图的顶点数．该文证明当n=2k+1时,该下界是可以达到的．

4一致C-超图的最小边数的上界(英文)

主要讨论了 4一致C 超图的最小边数与最小上色数的关系 ,给出了上色数为 3的 4一致C 超图的最小边数的一个上界 .

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

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

给定色可行集的极大混合超图

若C=D,则混合超图H=(X,C,D)称为bi-超图.向量R(H)=(r1,r2,…,rχ珋)表示超图H的色谱,其中ri(i=1,2,…,χ珋)表示H的不同的严格i-染色的数目,χ珋表示H的上色数.证明了对于一个确定的可行集,存在一个bi-超图有任意多的边数和点数,部分解决了由Voloshin提出的公开问题.

一类弱惟一染色B-超图的构造及其最小点数

定义了弱惟一染色B-超图,给出了一种构造弱惟一染色B-超图的方法,称为直角三角形构造法,并讨论了由直角三角形构造法得到的弱惟一染色B-超图的最小点数.