共查询到18条相似文献,搜索用时 62 毫秒
1.
图的条件色数是经典色数的推广,确定图的条件色数问题是一个NPC问题。已知广义Petersen图的3-条件色数的上界是8。证明了广义Petersen图3-条件色数的下界是4,并刻画了达到此下界的广义Petersen图。 相似文献
2.
大边数图的星约束色数 总被引:1,自引:0,他引:1
图的P-色数χ(G,P)是对G的顶点着色,使得每一色类的导出子图具有性质P的最小颜色数,该文研究χ(G,P),这里P是星的并这一性质,且把这种P-色数星约束色数,记为χ(G,St),该文给出一些大边数图的星约束色数。 相似文献
3.
证明了对于围长不少于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. 相似文献
4.
5.
许振宇 《济南大学学报(自然科学版)》2008,22(2):197-199
图G膨胀图是指将G的每一个点都用一个完全图替换,且取代两个不同顶点u和v的完全图上的两点相邻当且仅当u和v是相邻的;若取代每个顶点的完全图都是同阶的,则称此膨胀图为一致的.证明了圈的一致膨胀图的关联色数不超过Δ(G) 2. 相似文献
6.
对整数k>0,r>0,图G的条件(k,r) 染色是一个从顶点集V(G)到数集{1,2,…,k}的映射c,使得:(1)相邻点获得的颜色不同;(2)|c(N(v))|≥min{|N(v)|,r}。G的条件色数是使得G有一个正常的(k,r) 染色的最小k值,记为χr(G)。本文主要研究了r取3时,几类特殊图的条件色数。 相似文献
7.
图的动态着色是Bruce Montgomery于2001年引入的一个新概念。本文分别证明了Halin图和非5圈的Series—Parallel图的动态色数都不超过4。 相似文献
8.
扇与Halin图的一致膨胀图的关联色数 总被引:3,自引:1,他引:2
设图G的点集V(G)={v1,v2,…vn},G的膨胀图R的点集V(FG)=V1UV2U…UVn,且对X∈K,y∈Vj,有xy∈E(FG),当且仅当i=j或ViVj∈E(G)。若对所有的i,满足|Vi|=t,则称其为G的一致膨胀图。给出了扇与△≥6的Hahn图的一致膨胀图的关联色数,它们均为该膨胀图的最大度加1。 相似文献
9.
10.
图的着色问题是图论中的一个重要问题,图论领域的诸多学者研究了图的各种着色.运用Lovsz局部引理,研究了图的星边着色(图G的星边着色是G的一个正常的边着色,并且使得G中无长为4的路是2-边着色的;图G的星边色数是G的所有星边着色中所使用的最小颜色数,记为χ’se(G)),并证明了最大度为Δ(Δ≥2)的简单无向图G的星边色数新的上界为χ’se(G)≤「9(Δ-1)3/2?. 相似文献
11.
单圈图和双圈图的动态色数 总被引:1,自引:0,他引:1
在对单圈图的性质进行分析的基础上,证明了单圈图的动态色数是3或4.构造了双圈图的子图H1和H2,证明了大部分双圈图的动态色数χd(G)=max{χd(H1),χd(H2)}.并给出了一个动态色数不是max{χd(H1),χd(H2)}的双圈图. 相似文献
12.
图G的一个正常全染色f称为是邻点可区别的,如果G中任何相邻点的点及其关联边的颜色集合不同.对一个图G进行邻点可区别的正常全染色所用最少颜色数称为G的邻点可区别全色数,记为xat(G).证明了xat(G)≤△(G)+2对任意的△(G)≥11且围长至少为4的平面图G成立. 相似文献
13.
设G,H是阶至少为2的简单图。图G与H的强直积是指这样一个图G□×H,其顶点集合为V(G)×V(H),并且(x1,x2)(y1,y2)∈E(G□×H)当且仅当[x1y1∈E(G)且x2y2∈E(H)]或者[x1=y1且x2y2∈E(H)]或者[x2=y2且x1y1∈E(G)]。一个图G的使用了k种颜色的2-距离染色是指一个从V(G)到{1,2,…,k}的映射f,使得任意两个不同的距离最多是2的顶点染不同的颜色。对图G进行2-距离染色所需的最少的颜色数称为图G的2-距离色数,记为χ2(G)。文中将获得两个图的强直积的2-距离色数的可达到的上界和下界:Δ(G□×H)+1≤χ2(G□×H)≤χ2(G).χ2(H)。对一些特殊图,例如Pm□×Kn,Pm□×Wn,Pm□×Sn,Pm□×Fn,Pm□×Cn(n≡0(mod3)或者n=5),给出了它们的2-距离色数。 相似文献
14.
张埂 《黑龙江科技学院学报》2010,20(4):315-317,322
为了研究简单图G的无圈边染色,利用线性一时间算法思想证明了最大顶点度为4的简单图G。如果G中任意一条边的两个端点的度数之和不超过6,则其无圈边色数不超过5。 相似文献
15.
16.
引入了一种新的图着色 :图的分数关联着色。定义了图的分数关联色数。讨论了分数关联着色的性质 ,给出了图的分数关联色数的一个下界。 相似文献
17.
图的边覆盖染色与分数边覆盖染色 总被引:4,自引:1,他引:3
讨论了图G=(V,E)的分数边覆盖色数χ′cf(G)的概念和性质,给出计算χ′cf(G)的一个精确公式,即χ′cf(G)=minS2·|C[S]||S|+1,其中S为V(G)的非空子集且|S|为奇数,C[S]是E(G)的至少有一个端点在S中的边构成的子集,并证明δ-1<χ′cf(G)δ;同时讨论了χ′cf(G)与图G的边覆盖色数χ′c(G)的关系,并利用χ′cf(G)与χ′c(G)的关系对图进行分类. 相似文献
18.
若干广义Petersen图的邻点可区别全染色 总被引:3,自引:1,他引:2
田双亮 《山东大学学报(理学版)》2008,43(9):42-44
研究了若干广义Petersen图G(n,r)的邻点可区别全染色。 构造性地证明了:若n≡0(mod 4),r0(mod 4)或n≡0(mod 5),r0(mod 5),则G(n,r)的邻点可区别全色数为5。 相似文献