图的点可区别Ⅳ-全染色

设G是简单图,图G的一个k-点可区别Ⅳ-全染色(简记为k-VDIVT染色)f是指一个从V(G)UE(G)到{1,2,…,k}的映射,满足:uv,uw∈E(G),v≠w,有f(uv)≠f(uw);u,v∈V(G),u≠v,有C(u)≠G(v),其中C(u)={f(u)}∪{f(uv)|uv∈E(G)}.数min{k|G有一个k-VDIVT染色}称为图的点可区别Ⅳ-全色数,记为χ_(vt)^(iv)(G).本文给出了双星S_(2n),轮W_n和扇F_n的点可区别Ⅳ-全色数.     

梯图的点可区别全染色Ⅵ

一个图的全染色被称为点可区别的即对任意两个不同点的相关联元素所构成的色集合不同.其中所用的最少颜色数称为G的点可区别全色数.定义了一种排序方法:三角排序.利用该排序的结果证明了当n≡6(mod 8)和C4n-1/2+2＜ m ≤C4n/2+2时,梯图Lm (≌) Pm×P2的点可区别全色数为n.     

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

通过构造邻点可区别Ⅰ-全染色函数得到了路、圈、星、扇和轮的倍图的邻点可区别Ⅰ-全色数,验证了它们满足邻点可区别Ⅰ-全染色猜想.     

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

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

关于图的邻点可区别全染色

提出了图的邻点可区别全染色的概念, 给出了圈、完全图、完全二部图、扇、轮和树的邻点可区别全色数.     

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

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

蛛网图及渔网图的邻点可区别I-全染色

通过揭示完全蛛网图和渔网图的结构特点,研究了它们的邻点可区别I-全染色问题,并运用构造法给出了其邻点可区别I-全染色,从而获得了它们的邻点可区别I-全色数.     

关于一类二部图的均匀邻点可区别全染色

若图的邻点可区别全染色的各色所染元素数之差不超过1,则称该染色法为图的均匀邻点可区别全染色,而所用的最少颜色数称为该图的均匀邻点可区别全色数.本文给出了一类二部图的均匀邻点可区别全染色数.     

图P_m□K_n的邻点可区别Ⅰ-全染色

应用构造具体染色的方法给出了m阶路和n阶完全图K_n的Cartesian积图的令β点可区别I-全染色得到了图P_m囗K_n的邻点可区别I-全色数.     

若干Mycielski's图的邻点可区别E-全染色

针对简单图G与Mycielski's图之间的关系,讨论了路、圈、星、扇、轮和完全图的Mycielski's图的邻点可区别E-全染色,给出了路、圈、星、扇、轮和完全图的Mycielski's图的邻点可区别E-全色数.     

一些分裂图的点可区别全染色

图G的一个k-正常染色被称为点可区别全染色指任意两点的点及其关联边所染色集合不同.研究了一些分裂图K_(2n+1)\E(K_m)(n≥4,m≥3)的点可区别全色数.     

若干Mycielski图的邻点可区别E-全染色

设G(V,E)是简单连通图,k是正整数,若V∪到{1,2,3,…,k}的映射f满足对任意uv∈E(G),有f(U)≠f(v),f(u)≠f(uv)f(v)≠f(uv),且C(u)≠C(v),其中C(u):{f(u)}∪{f(uv)|uv∈E(G)}.那么称f为G的k-邻点可区别的E-全染色(简记为k-AVDETC),并称X_(at)~e(G)=min{k|G有k-邻点可区别的E-全染色}为G的邻点可区别的E-全色数.本文讨论了路、圈、扇、星、轮及完全图的Mycielski图的邻点可区别E-全染色,得到了该类图的邻点可区别的E-全色数.     

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

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

一些图的Double图的点可区别全色数

文献【2】定义点可区别全染色,对—个图其所用最少染色数称为它的点可区别全色数．本文得到了星、扇和轮的Double图的点可区别全色数．     

一些图的倍图与Mycielski图的邻点可区别VE-全染色

对简单图G(V,E),存在一个正整数κ,使得映射f:V(G)U E(G)→{1,2…,κ},如果对uv∈E(G),有f(u)≠f(uv),f(v)≠f(uv),且C(u)≠C(v),则称f是图G的邻点可区别VE-全染色,且称最小的数κ为图G的邻点可区别VE-全色数,讨论了路、圈、星、扇、轮等一些图的倍图与Mycielski图的邻点可区别VE-全色数。     

一类正则循环图的Cartesian积图的D(β)-点可区别VI-全染色及I-全染色

设G是简单图,若图G的全染色f满足:1)(?)uv,vw∈E(G),有f(uv)≠f(vw);2)(?)uv∈E(G),u≠v,有f(u)≠f(v);3)(?)u,v∈V(G),0相似文献   

仙人掌图的邻点被扩展和可区别全染色

设G为简单图.G的全k-染色是指k种颜色1,2,…,k对图G的全体顶点及边的一个分配.设c是图G的一个全k-染色,任意的x∈V(G),称■为点x的扩展和,其中N(x)={y∈V(G)|xy∈E(G)}.称图G的全k-染色c为邻点被扩展和可区别(简记为NESD),如果w(x)≠w(y),其中xy∈E(G).使得图G存在NESD全k-染色的最小值k被称为图G的邻点被扩展和可区别全色数,简记为egndi_∑(G).本文利用数学归纳法探讨了仙人掌图的邻点被扩展和可区别全染色,并证明了这类图的邻点被扩展和可区别全色数不超过2.该结论说明Flandrin等人提出的NESDTC猜想对于仙人掌图是成立的.     

轮与星的多重联图的邻点可区别E-全染色

G(V,E)是一个简单图,k是一个正整数,f是一个V(G)UE(G)到{1,2,…,k}的映射.如果■u,v∈V(G),则f(u)≠f(v),f(u)≠f(uv),f(v)≠f(uv),C(u)≠C(v),称f是图G的邻点可区别E-全染色,称最小的数k为图G的邻点可区别E-全色数.给出了轮与星的多重联图的邻点可区别E-全色数.     

广义θ-图的邻点可区别的全染色

u,v两点间连多于三条内部不相交的路且至多有一条长度为1的图,称为广义θ-图.本文给出了广义θ-图的邻点可区别的全染色.