强边着色猜想问题的最优图

著名图论专家Erds和Nesetǐil对图的强边色数上界提出了一个猜想:当最大度Δ为偶数时,χ's(G)≤5/4Δ~2;当最大度Δ为奇数时,χ's(G)≤1/4(5Δ~2-2Δ+1);并且给出了当Δ=4时的最优图.此处构造了一族图,并证明了当最大度为奇数时,如果Erd9s和Ne2etǐil提出的强边着色猜想成立,则猜想中的上界是最优的.     

关于强边着色猜想的最优图问题

著名图论专家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提出的强边着色猜想成立,则猜想中的上界是最优的.     

最大度等于5的图的强边色数

最大度等于5的图的强边色数至多为38.     

一类平面图的强边着色

图G的强边着色是正常边着色且任何长为3的路的边不着双色.图G的强边色数是G的所有强边着色中使用色数的最小者,记为χ′s(G).证明了如果图G是平面图且满足g(G)≥14,则χ′s(G)≤|(5Δ2-2Δ+1)/4|,其中g(G)表示图G的围长.     

完全偶图和路的强边着色

研究了完全偶图和路, 并证明了两个结论.     

乘积图与正则图的满着色

图G=(V，E)的一个正常着色就是将G的顶点划分为独立集，或称之为色类，记为П=|V1，V2，…VK|．对于任一色类Vi中的点v，如果它与其余色类中至少一个点相邻，则”被称为是满色的．如果在一个正常着色中，所有点都是满色的，则称这样的着色是满着色．如果一个图存在满着色，定义图的满着色数为使得图存在满着色的最小颜色数，记为xf(G)．另外，记f(G)为使图存在满着色的最大颜色数．在这篇文章中，我们研究了一些乘积图的满着色，得出一些关于正则图的满着色的结果．     

两类幂图的强边染色

图的强边染色是在正常边染色的基础上,要求每个色类的导出图是一个匹配。本文通过构造法,研究了路的幂图的强边色数至多是9,圈的幂图的强边色数至多是14。     

S_(m,n)图的强边色数及点可区别全色数

文章得到了星Sm,n(m≥n≥1)的强边色数χs′(Sm,n)=m+n+1及点可区别全色数χvt(Sm,n)=m+n+2.     

网格图的剖分图的强边染色

研究了3种网格图的剖分图的强边着色.网格图的剖分图是指用一个长为2的路去替换网格图的每条边.具体给出了六边形、四边形、三角形的网格剖分图的一种着色方法,以此为基础证明了Sχ′(Γs6)=4,Sχ′(Γs4)=5,Sχ′(Γs3)=7.     

一类正则图的邻强边染色

研究一类正则图G(n,n,r)(n=1,2(mod 3))的邻强边染色. 用构造性方法给出了一类正则图的邻强边染色, 验证了对|V(G)|≥3的连通图G（V,E）(G(V,E)≠C₅), 有Δ(G)≤χ′_αs(G)≤Δ(G)+2成立.     

几类冠图的邻强边色数

图的强染色来自计算机科学,有着很强的实际背景,但确定图的强色数是非常困难的。张忠辅,刘林忠,王建方等研究了图的邻强边染色,并提出了邻强边染色猜想：对任意连通图GG,{y}≥3且G≠C5有△≤X’ax（G）≤△＋2。研究了树、圈、扇、轮、完全二部图及完全图的冠图的邻强边色数;证明了：△≤X’as（G）≤△＋1,且X’as（G）≤△＋1当且仅当G[V△]≠Ф。     

一类图的邻强边色数的上界

证明了当图G的最大度Δ(G)恰以n的某个函数为界时,G的邻强边色数χ′as(G)≤│cn│,其中0相似文献   

路和圈的广义Mycielski图的邻强边色数

研究了路和圈的广义Mycielski图的邻强边染色,证明了对P个点的路Pp≥2),Xa(Mn(Pp))={4 p=3.对圈Cp,有Xa(Mn(Cp))=5.     

两类图的点可区别边染色数

证明了,任意正整数k≥2,存在点可区别边色数为2k+1的k+1-正则图;任意正整数m≥4,存在点可区别边色数为m的偶图.     

幂图的邻点可区别全色数和邻点可区别-VE全色数

根据路的幂图Pkn的结构性质,用穷染、递推的方法,讨论了Pkn的邻点可区别全染色和邻点可区别-VE全染色,得到了相应的色数,并给出了一种染色方案.     

图的相邻强边着色数

如果在一个图的正常边着色中,相邻两点关联的边集所着的颜色集合不同,则称此正常边着色为相邻强边着色.对图G进行相邻强边着色所需要的最小色数称为G的相邻强边着色数,记作X'as(G).给出了相邻强边着色数的两个上界:一是对于任何d-正则图G(d≥3),X'as(G)≤16d;二是如果图G有两个边不交的完美匹配,则X'aa(G)≤3△(G) 1.     

低度外平面图的点强全染色

图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。     

两类冠图的点边邻点可区别全染色

 图的染色理论是图论的一个重要研究领域,求解图的色数被认为是一个NP-hard问题。对简单连通图G(V,E),存在一个正整数k,使得映射f :V(G)∪ E(G)→{1,2,…,K},如果对∀uv∈E(G),有f(u)≠f(uv),f(v)≠f(uv),且C(u)≠C(v),则称f是图G的点边邻点可区别全染色(又称为邻点可区别VE-全染色),而χ_at^ve (G)=min{k|k－VE－AVDTC},称为G的点边邻点可区别边色数(又称为邻点可区别VE-全色数),其中色集合C(u)={f(u)}∪{f(uv)|uv∈E(G)}。本文构造了两类冠图C_m·S_n和C_m·P_n,研究了两类冠图C_m·S_n和C_m·P_n的点边邻点可区别全染色。根据C_m·S_n和C_m·P_n的结构性质,用穷染递推的方法,得到了它们的相应色数,给出一种染色方案。