k-方图的邻点可区别无圈边染色

图G的一个正常边染色被称作邻点可区别无圈边染色,如果G中无二色圈,且相邻点关联边的色集合不同.图G的邻点可区别无圈边色数记为χ′_^(aa)(G),即图G的一个邻点可区别无圈边染色所用的最少颜色数.通过构造具体染色的方法,给出了一些k-方图的邻点可区别无圈边色数.     

关于图K_(2n)-E(C_4)的点可区别边色数

图G的一个k-正常边染色f被称为点可区别边染色是指任何两点的点及其关联边的色集合不同,所用最小的正整数k被称为G的点可区别边色数,记为x′_(vd)(G).用K_(2n)-E(C_4)表示2n阶完全图删去其中一条4阶路的边后得到的图,文中得到了K_(2n)-E(_4)的点可区别边色数.     

扇的倍图的邻点可区别边色数

设G(V,E)是阶数至少是3的简单连通图,若f是图G的k-正常边染色,使得对任意的uv∈E(G),C(u)≠C(v),那么称f是图G的k-邻点可区别边染色(k-ASEC),其中C(u)={f(uw)│uw∈E(G)},而χa′s(G)=min{k│存在G的一个k-ASEC},称为G的邻点可区别边色数.本文给出扇的倍图D(Fm)的邻点可区别边色数.     

若干倍图的邻点可区别Ⅵ-全染色

图的一个边正常的全染色满足相邻点的色集合不同时被称为邻点可区别Ⅵ-全染色,把所用的最少颜色数称为邻点可区别Ⅵ-全色数,其中任意一点的色集合为点上与关联边所染的颜色构成的集合.应用构造邻点可区别Ⅵ-全染色函数法得到了路、圈、星和扇的倍图的邻点可区别Ⅵ-全色数,进一步验证图的邻点可区别Ⅵ-全染色猜想.     

图的邻点可区别无圈边染色的一个界

图G的一个正常边染色被称作邻点可区别无圈边染色,如果G中无二色圈,且相邻点关联边的色集合不同.应用概率的方法得到了图G的一个邻点可区别无圈边色数的上界,其中图G为无孤立边的图.     

图C_5∨K_t的邻点可区别全色数

设f是图G的一个正常全染色.对任意x∈V(G),令C(x)表示与点x相关联的边的颜色以及点x的颜色所构成的集合.若对任意uv∈E(G),有C(u)≠C(v),则称.f是图G的一个邻点可区别全染色.对一个图G进行邻点可区别全染色所需的最少的颜色的数目称为G的邻点可区别全色数,记为Xat(G).用C_5∨K_t表示长为5的圈与t阶完全图的联图.讨论了C_5∨K_t的邻点可区别全色数.利用正多边形的对称性构造染色以及组合分析的方法,得到了当t是大于等于3的奇数以及t是偶数且2≤t≤22时,X_(at)(C_5 V K_t)=t+6,当t是偶数且t≥24时,X_(at)(C_5 V K_t)=t+7.     

图K_(3,4)∨K_t的点可区别正常边染色

设f是图G的一个正常边染色.对任意x∈V(G),令S(x)表示与点x相关联的边的颜色所构成的集合.若对任意u,v∈V(G),u≠v,有S(u)≠S(v),则称f是图G的一个点可区别正常边染色.对一个图G进行点可区别正常边染色所需的最少的颜色的数目称为G的点可区别正常边色数,记为χ_s'(G).讨论了图K_(3,4)∨K_t的点可区别正常边染色及其色数,利用正多边形的对称性构造染色以及组合分析的方法,确定了图K_(3,4)∨K_t的点可区别正常边色数,得到了当t是大于等于2的偶数以及t是奇数且3≤t≤25时,χ_s'(K_(3,4)∨K_t)=t+7;当t是奇数且t≥27时,χ_s'(K_(3,4)∨K_t)=t+8.     

图的Smarandachely邻点边色数的界

对图G的一个k-正常变染色法f,若图G中任意相邻两点的相邻边色集合互相不包含,那么称f为图G的一个k-Smarandachely邻点边染色(简记为k-SEC),而最小的正整数k称为图G的Smarandachely邻点边色数.尝试应用Lovasz局部引理来得到了Smarandachely邻点边色数的上界.     

关于K_(2n)-E(C_m)的点可区别边色数

图G的一个k-正常边染色f被称为点可区别边染色是指任何两点的点及其关联边的色集合不同,所用最小的正整数k被称为G的点可区别边色数,记为X'_(vd)(G).用k_(2n)-E(C_m)表示2n阶完全图删去其中一条m阶路的边后得到的图,得到了K_(14)-E(C_4),K_(16)-E(C_4),K_(18)-E(C_5),K_(20)-E(C_5)的点可区别边色数分别为14,16,18,20.     

围长至少为6的平面图的邻点可区别边染色

邻点可区别边染色是指图G有一个正常边染色且任意两个相邻顶点的颜色集合不相等.邻点可区别边色数是指使图G有一个邻点可区别边染色的最小颜色数值,记作χ_α’(G).本文证明了:若图G是围长至少为6的正常平面图,则有χ_α’(G)≤max{6,△(G)+1}.     

图的邻点可区别全染色的渐近性质

图G的一个正常全染色被称为邻点可区别全染色,如果G中任意两个相邻点的色集合不同,其所用的最少颜色数称为邻点可区别全色数.张忠辅老师猜想:对于|V(G)|≥3的连通图G,其邻点可区别全色数最多不超过△(G)+3.用概率方法证明了对简单图G,△≥14,有χ_(at)(G)≤△+C,其中C≥10~(26)+1.     

路与星、扇、轮图的积图的邻点可区别I-全染色

图G的I-全染色是指若干种颜色对图G的顶点和边的一个分配,使得任意两个相邻顶点的颜色不同,任意两条相邻边的颜色不同.在图G的一个I-全染色下,G的任意一个点的色集合是指该点的颜色以及与该点相关联的全体边的颜色构成的集合.图G的一个I-全染色称为是邻点可区别的,如果任意两个相邻点的色集合不相等.对一个图G进行邻点可区别I-全染色所用的最少颜色的数目称为图G的邻点可区别I-全色数.应用构造具体染色的方法给出了路与星、扇、轮图的积图的邻点可区别I-全色数     

关于图的点可区别边染色的一个猜想

图G的一个k-正常边染色f被称为点可区别的是指任意两个不同点的点及其关联边所染色集合不同,所用最少染色数被称为G的点可区别边色数,张忠辅教授提出一猜想即对每一个正整数k≥3,总存在一个最大度为△(G)=k≥3的图G,,满足图G一定有一个子图H,且母图的点可区别的边色数小于子图的.本文证明了对于最大度小于9时,此猜想正确.     

关于图的点可区别边染色猜想的一点注

图G的一个k-正常边染色f被称为点可区别的是指任意两点的点及其关联边所染色集合不同,所用最少颜色数被称为G的点可区别边色数,张忠辅教授提出一个猜想即对每一个正整数k≥3,总存在一个最大度为△(G)=k≥3的图G,图G一定有一个子图H,使得G的点可区别的边色数不超过子图的.本文证明了对于最大度△≤6时,猜想正确.     

图的半强积的邻点可区别染色

两个简单图G与H的半强积G·H是具有顶点集V(G)×V(H)的简单图,其中两个顶点(u,v)与(u',v')相邻当且仅当u=u'且vv'∈E(H),或uu'∈E(G)且vv'∈E(H).图的邻点可区别边(全)染色是指相邻点具有不同色集的正常边(全)染色.统称图的邻点可区别边染色与邻点可区别全染色为图的邻点可区别染色.图G的邻点可区别染色所需的最少的颜色数称为邻点可区别染色数,并记为X_a~((r))(G),其中r=1,2,且X_a~((1))(G)与X_a~((2))(G)分别表示G的邻点可区别的边色数与全色数.给出了两个简单图的半强积的邻点可区别染色数的一个上界,并证明了该上界是可达的.然后,讨论了两个树的不同半强积具有相同邻点可区别染色数的充分必要条件.另外,确定了一类图与完全图的半强积的邻点可区别染色数的精确值.     

Halin图的邻和可区别边染色与边权点染色

记[k]={1,2,…,k),称为颜色集.设φ:E(G)→[k]为图G的边集合到[k]的映射,令f(v)表示与顶点v关联的边的颜色的加和.如果对任意一条边uv∈E(G),都有φ(u)≠φ(v),f(u)≠f(v),则称φ为图G的邻和可区别[k]-边染色,k的最小值称为图G的邻和可区别边色数,记为ndi_Σ(G).若对任意一条边uv∈E(G),都有f(u)≠f(v),则称φ为图G的k-边权点染色,称图G是k-边权可染的.运用组合零点定理证明了对于最大度不等于4的Halin图有:ndi_∑(G)≤Δ(G)+2,并证明了任一Halin图是4-边权可染的.     

图的邻点全和可区别全染色

设f:V(G)∪E(G)→{1,2,…,k}是图G的一个正常k-全染色。令■其中N(x)={y∈V(G)|xy∈E(G)}。对任意的边uv∈E(C),若有Φ(u)≠Φ(v)成立,则称f是图G的一个邻点全和可区别k-全染色。图G的邻点全和可区别全染色中最小的颜色数k叫做G的邻点全和可区别全色数,记为f tndi∑(G)。本文确定了路、圈、星、轮、完全二部图、完全图以及树的邻点全和可区别全色数,同时猜想:简单图G(≠K2)的邻点全和可区别全色数不超过△(G)+2。     

若干联图的邻点可区别-点边全染色

设G(V,E)是简单图,k是正整数.从V(G)∪E(G)到{1,2,…,k}的映射f被称作G的邻点可区别-点边全染色,当且仅当:■uv∈E(G),f(u)≠f(uv),f(v)≠f(uv),■uv∈E(G),C(u)≠C(v),且称最小的数k为G的邻点可区别-点边全色数.其中C(u)={f(u)}∪{f(uv)|uv∈E(G)},研究了一些联图的邻点可区别-点边全染色法,得到了它们的色数.     

关于积图点可区别边染色的若干结论

如果图G的一个正常边染色满足任意两个不同点的关联边色集不同, 则称为点可区别边染色(VDEC), 其所用最少颜色数称为点可区别边色数. 利用构造法给出了积图点可区别边染色的一个结论, 得到了关于积图点可区别边色数的若干结果, 并且给出25个具体积图的点可区别边色数, 验证了它们满足点可区别边染色猜想(VDECC).     

关于Cm ∨ Cn和Cm ∨ Sn的点可区别边色数

对图G的正常边染色,若满足不同点的点所关联边色集合不同,则称此染色法为点可区别的边染色法,其所用最少染色数称为该图的点可区别边色数.本文得到了Cm∨Cn和Cm∨Sn的点可区别边色数.