共查询到20条相似文献,搜索用时 46 毫秒
1.
2.
许宝刚 《山东大学学报(自然科学版)》1996,31(4):384-387
图G的全色数xT(G)是使得VE9G)中相邻接或相关联的元素均着不同颜色的最少颜色数,证明了:如果v(G)=v(H),存在v∈V(G),V‘∈V(H)使得G^c-v和C-v’都含有完美对集且Δ(G)=Δ(H)并存在e∈E(G-v),e‘∈E(H-v’),使得G-e和H-e‘都是第一类图,或ΔG)〈(H)且存在e∈E(H-v’)使得H-e‘是第一类图,则xT(GVH)≤Δ(GVH)+2。 相似文献
3.
证明对于任意区间图和强弦图-全着色猜想成立,并且给出了区间图和强弦图的最优线性地,其算法复杂度仅为O(V+E)。 相似文献
4.
谢德政 《重庆工商大学学报(自然科学版)》2005,22(1):4-5
设G是一个图,G的全着色是一个映射π:V(G)YE(G)C,使得相关联或相邻的元素着不同色;G的所有全着色中,使得色数的最小者,称为G的全色数,记为χT(G);得到了几个特殊图的全色数 相似文献
5.
本文证明对乘积图G×Pn和G×Cm,若G∈C1T,则G×Pn∈C1T,G×C2m∈C1T和G×Cm∈C1TC2T;从而证明了乘积图Pr1×Pr2...×Pm∈C1r,Cr1×Cr2...×Cm∈C1T∪C2T.由此证明了对于这些图全着色猜想成立. 相似文献
6.
对于图G=(V,E),一个正常全着色就是从VUE到一个整数集的映射,使VUE中的任意两个相邻或相关联的元素都着不同的颜色,图G=(V,E)的全色数xτ(G)定义为xT(G)=min{k|存在G的一个正常k-全着急},本文对一类特殊图-含圈图的全着色给出了几个定理,验证了全着色猜想。 相似文献
7.
8.
引入了一种研究图全着色问题的新方法,即从考虑图中的圈出发研究全着色问题.运用该方法确定了一些图的全色数,并给出了图全色数的一个上界. 相似文献
9.
许宝刚 《山东大学学报(理学版)》1996,(4)
图G的全色数x_T(G)是使得VE(G)中相邻接或相关联的元素均着不同颜色的最少颜色数。证明了:如果ν(G)=ν(H),存在υ(?)V(G),υ'(?)V(H)使得G~c—υ和H~c—υ'都含有完美对集且△(G)=△(H)并存在e(?)E(G—υ),e'(?)E(H—υ'),使得G—e和H—e'都是第一类图,或△(G)<△(H)且存在e(?)E(H—υ')使得H—e'是第一类图,则x_T(GVH)≤△(GVH)+2g. 相似文献
10.
11.
简单图的全染色是图的染色理论中的一个重要问题,为了深入研究图的全色数猜想与图的最大平均度之间的关系,我们利用差值转移方法证明了最大平均度小于4的简单图的全色数满足全色数猜想;同时,还证明了最大度不小于12且最大平均度小于6的简单图G的全色数不超过Δ(G)+3. 相似文献
12.
设G是具有顶点集{t0,t1,…,tn-1}的轮,或扇,或星,其中t0为最大度点,且n≥5.G[hn]是图G与顶点不相交图序列hn=(Hi)i∈{0,1,…,n-1}的广义字典积,其中每一个Hi为m阶简单图.论文得到了以下结果:(1)若H0为完全图的补图,则G[hn]的全色数为(n-1)m+1;(2)若H0为完全图,则G[hn]的全色数为mn;(3)若H0为二部图,则G[hn]的全色数为Δ(H0)+(n-1)m+1,其中Δ(H0)表示图H0的最大度;(4)若H0为m阶圈,m≥3,则G[hn]的全色数为(n-1)m+3. 相似文献
13.
图的邻点可区别全染色,相对于图的正常全染色有更强的要求,因为它要求相邻顶点具有不同的颜色集合.本文刻画了两类特殊的完全多部图、广义圈和广义Mycielski图的邻点可区别全色数. 相似文献
14.
对扇,轮,完全二部图作了简单的剖分,得到了它们的剖分图,并得到了其剖分图的邻点可区别全色数. 相似文献
15.
双外平面图是一个平面图,它可以嵌入到平面上并使得它的顶点出现在两个面的边界上.设G是一个双外平面图,V(G)、E(G)、F(G)分别为双外平面图G的点集、边集和面集.G的全色数XT,(G)是使得V(G)∪E(G)中的任意相邻或相关联的两个元素均染不同颜色的最少颜色数.本文证明了最大度至少是6的2连通的特殊双外平面图G的全色数是△(G) 1,其中△(G)为G的最大度数. 相似文献
16.
研究一些倍图的邻点可区别均匀全染色(AVDETC), 利用构造法和匹配法给出了偶阶完全图、 偶阶圈、 路、 星和轮的倍图的邻点可区别均匀全色数, 并验证了它们满足邻点可区别均匀全染色猜想(AVDETCC). 相似文献
17.
图G的一个正常全染色如果满足G中任意路长为2的点和边着色均不相同时,称为G的星全染色.图的全部k-星全染色中所用最少的颜色数称为图G的星全色数.得到了路与星、轮、扇的笛卡尔积图的星全色数. 相似文献
18.
《西北民族学院学报》2010,(4)
图G的一个正常全染色如果满足G中任意路长为2的点和边着色均不相同,称为G的星全染色.图的全部k-星全染色中所用最少的颜色数称为图G的星全色数.文章研究了若干联图的星全色数. 相似文献
19.
图G的一个k-点强全染色是指图G的正常全染色f,若任意x,y∈N[υ],有f(x)≠f(y),简记为k-VSTC,称xT^υ5(G)=min{k/G有k-VSTC}为G的点强全色数。研究了低度外平面图的点强全染色,证明了对△(G)=3的外平面图G有4≤xT^υs(G)≤5。 相似文献
20.