共查询到14条相似文献,搜索用时 46 毫秒
1.
图G的一种均匀k-边染色是指用k种颜色去染G的边使得对G的每一个顶点v,任何两种颜色染与。相关联边的数目最多相差1.证明了对任意的大于3的整数k,Halin图都有均匀k-边染色;讨论了k=3的情况. 相似文献
2.
3.
图G的一种均匀k 边染色是指用k种颜色去染G的边使得对G的每一个顶点v ,任何两种颜色染与v相关联边的数目最多相差 1.证明了对任意的大于 3的整数k,Halin图都有均匀k 边染色 ;讨论了k=3的情况 相似文献
4.
张埂 《黑龙江科技学院学报》2010,20(4):315-317,322
为了研究简单图G的无圈边染色,利用线性一时间算法思想证明了最大顶点度为4的简单图G。如果G中任意一条边的两个端点的度数之和不超过6,则其无圈边色数不超过5。 相似文献
5.
陈勇 《山东大学学报(理学版)》2006,41(1):111-114
给定无向简单图G=(V,E)与颜色集C,并且对C中的每一种颜色c设定一个费用值w(c)∈R+.全染色是给出图的一个可行染色使得相关联的边和点、相邻的点或边都染不同的颜色.定义了费用全染色问题,即求解最优的全染色f,使得染色费用和最小,对于树图T,给出了一个2-近似算法,该算法的运行时间为O(nΔ2). 相似文献
6.
石少俭 《曲阜师范大学学报》1998,24(4):118-119
图的染色是图论的重要研究内容之一.平面图染色是其中的一个主要方面.有各种各样的染色方式,近来,又出现了列表染色[1].定义1称图G是k-边可选择的.如果任给e∈E(G),和边e的任给颜色集L(e),|L(e)|=t,都可以选一种颜色σ(e)∈L(e)... 相似文献
7.
冠图Cm(0)Sn的点可区别的均匀边染色 总被引:1,自引:0,他引:1
主要研究了一类特殊图--冠图的点可区别的均匀边染色,讨论过程中主要采用组合的方法,分别研究不同情况下该类图的染色方法,验证点可区别的均匀边染色数界的猜想μ(G)≤X'vde(G)≤μ(G)+1.该方法对解决此类图的染色均是正确有效的. 相似文献
8.
关于Kn-{vn-5vn-4,vn-3vn-2,vn-1vn}(n≥14,n≡0(mod2))的点可区别边色数 总被引:1,自引:0,他引:1
给出了图KKn-{vn-5vn-4,vn-3vn-2,vn-1vn}(n≥14,n≡0(mod2))的点可区别边色数,其中Kn为n阶完全图。 相似文献
9.
给出了图K_n-{v_(n-5)v_(n-4),v_(n-3)v_(n-2),v_(n-1)v_n}(n≥14,n≡0(mod2))的点可区别边色数,其中Kn为n阶完全图。 相似文献
10.
文章给出了边列表染色和顶点列表染色的定义,证明了对轮图,边选择数x (G)=△(G),点选择数xLV(G)=4,点边选择数xLVE(G)=△(G)+1. 相似文献
11.
图G的强边着色是正常边着色且任何长为3的路的边不着双色.图G的强边色数是G的所有强边着色中使用色数的最小者,记为χ′s(G).证明了如果图G是平面图且满足g(G)≥14,则χ′s(G)≤|(5Δ2-2Δ+1)/4|,其中g(G)表示图G的围长. 相似文献
12.
13.
张卫标 《重庆工商大学学报(自然科学版)》2017,34(3):21-23
著名图论专家Erds和Nesetǐil对图的强边色数上界提出了一个猜想:当最大度Δ为偶数时,χ's(G)≤5/4Δ~2;当最大度Δ为奇数时,χ's(G)≤1/4(5Δ~2-2Δ+1);并且给出了当Δ=4时的最优图.此处构造了一族图,并证明了当最大度为奇数时,如果Erd9s和Ne2etǐil提出的强边着色猜想成立,则猜想中的上界是最优的. 相似文献
14.
图G的正常边染色称为是点可区别的, 如果对G的任意两个不同的顶点u,v, 与u关联的边的颜色构成的集合异于与v关联的边的颜色构成的集合。 对图G进行点可区别正常边染色所需要的最少颜色数称为是G的点可区别正常边色数, 记为χ′s(G)。讨论了图K3,3∨Kt 的点可区别正常边染色。 相似文献