共查询到20条相似文献,搜索用时 31 毫秒
1.
2.
图G的一个k-正常边染色,若满足任意两个相邻点的色集合中所有元素之和不同,则称该染色为图G的一个k-邻和可区别边染色。其中,k的最小值称为图G的邻和可区别边色数。运用分析法与数学归纳法,研究了单圈图的邻和可区别边色数。 相似文献
3.
设G是具有顶点集V(G)和边集E(G)的简单图。如果G的一正常边染色σ满足对任意uv∈E(G),有Cσ(u)≠Cσ(v),其中Cσ(u)为点u的关联边所染颜色构成的集合,则称σ为G的邻点可区别边染色。如果G的一正常全染色σ满足对任意uv∈E(G),有Sσ(u)≠Sσ(v),其中Sσ(u)表示点u及u的关联边所染颜色构成的集合,则称σ为G的邻点可区别全染色。图G的邻点可区别边(或全)染色所需的最少的颜色数,称为G的邻点可区别边(或全)色数,并记为χ’as(G)(或χat(G))。给出了图G的倍图D(G)的以上两个参数的上界,并对完全图与树,确定了它们的倍图的邻点可区别边色数与全色数的精确值。 相似文献
4.
令[k]={1,2,…,k},Φ为图G的一个正常[k]-全染色。用f(v)表示点v及所有与其关联的边的颜色的加和,如果对任意边uv∈E(G),有f(u)≠f(v),则称该染色为图G的[k]-邻和可区别全染色。k的最小值称为图G的邻和可区别全色数,记为χ″Σ(G)。Pils'niak和Woz'niak提出猜想:对任意简单图G,有χ″Σ(G)≤Δ(G)+3,其中Δ(G)表示图G的最大度。运用组合零点定理证明了该猜想对于任一Halin图成立。 相似文献
5.
中间图的邻点可区别全染色 总被引:1,自引:0,他引:1
设G是简单连通图,G的k-正常全染色f称为是邻点可区别的,如果对G的任意相邻的两顶点,其点的颜色及关联边的颜色构成的集合不同,称f为G的k-邻点可区别全染色,这样的k中最小者称为G的邻点可区别全色数,本文考虑了图的中间图的邻点可区别全色数,并确定了路、圈、星图和扇图的中间图的邻点可区别全色数. 相似文献
6.
研究了圈Cp和完全图Kp的Mycielski’s图的邻强边染色和邻点可区别全染色的问题,得到了如下结果:如果连通图G(V,E)满足Xa'(G)=△(G),则Xa'(Mn(G))=△(Mn(G));圈的Mycielski‘s图的邻强边色数为5;P阶完全图的Mycielski’s图的邻点可区别全染色为2p. 相似文献
7.
讨论了Mycielski图M(Pn)、M(Cn)、M(Sn)、M(Fn)、M(Wn)的邻点扩展和可区别全染色问题.根据图形的结构特点,采用函数构造法,得到了这几类图的邻点扩展和可区别全色数,同时证明NESD猜想对上述5种My-cielski图是成立的. 相似文献
8.
9.
孟献青 《内蒙古师范大学学报(自然科学版)》2015,(1):4-7,11
根据圈的立方图的性质,利用穷染、置换的方法,研究了立方图C3n的邻点可区别全染色及一般邻点可区别全染色.通过设计染色方案,给出了立方图C3n的邻点可区别全色数及一般邻点可区别全色数指标,且色数均可取到下界. 相似文献
10.
图G的正常[k]-边染色σ是指颜色集合为[k]={1,2,…,k}的G的一个正常边染色。用w_σ(x)表示顶点x关联边的颜色之和,即■,并称w_σ(x)为x关于σ的权。图G的k-邻和可区别边染色是指相邻顶点具有不同权的正常[k]-边染色,最小的k值称为G的邻和可区别边色数,记为χ′_∑(G)。本文给出了两条不同阶路的联的邻和可区别边色数的精确值。另外,得到了同阶路的邻和可区别边色数的上界。 相似文献
11.
《西北民族学院学报》2017,(4):1-5
图G的一个[k]-邻和可区别全染色是图G的一个[k]-全染色,其中f(v)表示点v以及所有和v相关联的边的颜色之和,满足对G的每一条边uv,都有f(u)≠f(v)成立.文章研究了无限路的四类积图的邻和可区别全染色,如无限路的笛卡尔积、直积、半强积与强积等,并得到了它们的邻和可区别全色数. 相似文献
12.
考虑路与路、 路与圈、 圈与圈三类联图的邻点全和可区别全染色问题, 通过构造边染色矩阵, 利用组合分析法和分类讨论的思想, 得到了路与路、 路与圈、 圈与圈三类联图的邻点全和可区别全色数的精确值. 相似文献
13.
用三种树染色算法和组合分析法, 完成对哈林图的邻和可区别边染色、 邻和可区别全染色以及邻点全和可区别全染色, 并证明1-2-3 猜想和1-2猜想对哈林图均成立. 结果表明, 哈林图的邻点全和可区别全色数不超过3. 相似文献
14.
进一步研究了平方图的邻点全和可区别非正常全染色问题:利用平方图的结构构造了路、圈、毛毛虫、广义星以及最大度为3且不含2度点的树的平方图,通过组合分析法得到上述5类平方图的邻点全和可区别非正常全色数. 相似文献
15.
16.
17.
利用穷举法和组合分析法讨论了齿轮图的邻强边染色和邻点可区别的全染色,通过构造具体染色得到了齿轮图的邻强边色数和邻点可区别的全色数. 相似文献
18.
李永艳 《重庆师范大学学报(自然科学版)》2021,38(1):57-63
[目的]为了得到两条路的积图的邻点扩展和可区别全色数.[方法]直接构造了两路的笛卡尔积、直积、半强积的邻点扩展和可区别全染色.[结果]得到这3类积图的邻点扩展和可区别全色数.[结论]证明了NESDTC猜想对于两路的笛卡尔积、直积、半强积成立. 相似文献
19.
20.
利用穷举法和组合分析法讨论了图Dn,4的邻点可区别边染色和邻点可区别全染色,通过构造具体染色得到了图Dn,4的邻点可区别边色数和邻点可区别全色数。 相似文献