共查询到18条相似文献,搜索用时 546 毫秒
1.
关于强边着色猜想的最优图问题 总被引:1,自引:1,他引:0
著名图论专家Erd(o)s和Ne(s)et(r)il对图的强边着色数上界提出了一个猜想:当△为偶数时,x's(G)≤5/4△2;当△为奇数时,x's(G)≤1/4(5△2-2△+1),他们给出了当△=4的时的最优图.此处构造了一族图,并以此证明了当△为偶数时,如果Erd(o)s和Ne(s)et(r)il提出的强边着色猜想成立,则猜想中的上界是最优的. 相似文献
2.
朱海洋 《山东理工大学学报:自然科学版》2008,22(5):39-43
针对1985年Erdǒs和Nesetǐil提出的强边一染色猜想:令G为图,若△(G)为偶数,则Sx’(G)≤5△^2(G)/4;若△(G)为奇数,则Sx’(G)≤5△^2(G)/4-A(G)/2+1/4。证明了对于令G为△(G)=4的图,若δ(G)≤3或围长g(G)≤4,则Sx’(G)≤21。 相似文献
3.
图G的强边着色是正常边着色且任何长为3的路的边不着双色.图G的强边色数是G的所有强边着色中使用色数的最小者,记为χ′s(G).证明了如果图G是平面图且满足g(G)≥14,则χ′s(G)≤|(5Δ2-2Δ+1)/4|,其中g(G)表示图G的围长. 相似文献
4.
5.
设f是图G的一个正常边着色,若在f下G中没有2-色圈,则称f是图G的一个无圈边着色,其所用最小色数为G的无圈边色数。N.Alon猜想对所有简单图,无圈边色数不超过其最大度加2。本文证明了该猜想对Halin图成立,且当Δ≤4时,其色数不超过5;当Δ≥5时,其色数等于最大度。 相似文献
6.
7.
证明了若G为最大度Δ(G)≤4且不含4,5,6-圈的平面图,则χ(G2)≤Δ(G)+7. 相似文献
8.
9.
图的点可区别无圈边色数的一个上界(英文) 总被引:2,自引:0,他引:2
图G的一个正常边染色f,若满足:1)G中无2-色圈;2)对于V(G)中的任意两点u和v,有C(u)≠C(v),这里C(u)={f(uw)|uw∈E(G)},则f叫做图G的一个点可区别无圈边染色.图G的点可区别无圈边色数,记为χ′_(vda)(G),是图G的一个点可区别无圈边染色所用色的最小数目.证明了若图G是一个最小度不小于5,且顶点数不超过30Δ~4的图时,χ′_(vda)(G)≤10Δ~2,其中Δ是图G的最大度. 相似文献
10.
刘存肃 《南开大学学报(自然科学版)》2020,53(2):14-21
给定一个图G=(V (G),E (G)),图G的(s,t)-松弛强边着色数是指使得图G有(s,t)-松弛强k边着色的最小k值,记作χ′((s,t))(G).证明了在图G中,如果mad (G)<3,Δ≤7,那么χ′((0,1))(G)≤3Δ-1;同时证明了对于任意一个平面图G,如果g (G)≥7,Δ≥4,那么χ′((0,1))(G)≤■ 相似文献
11.
图G的一种均匀k 边染色是指用k种颜色去染G的边使得对G的每一个顶点v ,任何两种颜色染与v相关联边的数目最多相差 1.证明了对任意的大于 3的整数k,Halin图都有均匀k 边染色 ;讨论了k=3的情况 相似文献
12.
给出了图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阶完全图。 相似文献
13.
关于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阶完全图。 相似文献
14.
15.
张埂 《黑龙江科技学院学报》2010,20(4):315-317,322
为了研究简单图G的无圈边染色,利用线性一时间算法思想证明了最大顶点度为4的简单图G。如果G中任意一条边的两个端点的度数之和不超过6,则其无圈边色数不超过5。 相似文献
16.
图G的正常边染色称为是点可区别的, 如果对G的任意两个不同的顶点u,v, 与u关联的边的颜色构成的集合异于与v关联的边的颜色构成的集合。 对图G进行点可区别正常边染色所需要的最少颜色数称为是G的点可区别正常边色数, 记为χ′s(G)。讨论了图K3,3∨Kt 的点可区别正常边染色。 相似文献
17.
研究n阶完全图Kn(n≥20,n≡0(mod2))去掉4条独立边后的点可区别边染色,并给出了图Kn-{v1v2,v3v4,v5v6,v7v8}(n≥20,n≡0(mod2))的点可区别边色数。 相似文献
18.
图G的正常边染色称为是点可区别的,如果对G的任意两个不同的顶点u,v,与u关联的边的颜色构成的集合异于与v关联的边的颜色构成的集合。对图G进行点可区别正常边染色所需要的最少颜色数称为是G的点可区别正常边色数,记为χ's(G)。讨论了图K3,3∨Kt的点可区别正常边染色。 相似文献