一类完全图生成的广义格子图的邻点可区别边染色

定义了一类2维广义格子图H2(G, n, m；k1, k2),并从图的结构出发,利用构造染色的方法,得到了图H2(K4, n, m；4,4)的邻点可区别边色数。     

图C2m×Pn与C2m×Cn的邻点可区别非正常边染色

设简单图G和图H的顶点集分别为V(G)={u1,u2,…,um}和V(H)={v1,v2,…,vn}.所谓G和H的Cartesian积G×H是指这样的一个图,其顶点集和边集分别为V(G×H)={wij|i=1,2,…,m,j=1,2,…,n},E(G×H)={wijwrs|i=r,vjvs∈E(H)或j=s,uiur∈E(G)}.在这篇文章里,我们讨论了笛卡儿积图C2m×Pn和C2m×Cn的邻点可区别边非正常边染色,并给出了相应色数.     

几类弱积图的邻点可区别一般边染色

讨论了弱积图邻点可区别一般边染色,给出了P_2n×K_m,C_2n×C_2m,C_2n+1×C_2m+1,C_2n+1×K_m的邻点可区别一般边色数,得到了当G和H都无孤立边且色数均至少为3时,G×H邻点可区别一般边色数至少为3的结论.     

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

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

一类3-正则图的关联邻点可区别全染色

对简单图G(V,E),f是从V(G)∪E(G)到{1,2,...,k}的映射,k是自然数,若f满足(1)uv∈E(G),u≠v,f(u)≠f(v);(2)uv,uw∈E(G),v≠w,f(uv)≠f(uw);(3)uv∈E(G),C(u)≠C(v);其中C(u)={f(u)}∪{f(uv)|uv∈E(G)};则称f是G的一个关联邻点可区别全染色.给出了一类3-正则重圈图Re(n,m)(m≥2,n≥3且n≡0(mod2))的关联邻点可区别全色数.     

图K2n\E（Fm）（n≥4,m≥2）的点可区别边染色

对简单图G(V,E),设f是从E(G)到{1,2,…,k}的映射,k为自然数,如果f满足:1)对任意的uv,uw∈E(G),v≠w,有f(uv)≠f(uw);2)对任意的u,v∈V(G),u≠v,有C(u)≠C(v).则称f为图G的k-点可区别边染色法,而最小的k被称为点可区别边色数(其中C(u)={f(uv)|uv∈E(G)}).研究了图K2n\E(Fm)(n≥4,m≥2)的点可区别边色数.     

若干积图的点可区别边染色

证明了:(1)两个n(n2)阶完全图的积图的点可区别边色数为2n. (2)对阶至少是3的完全图Kn,若χ′vd(G)=Δ(G),则χ′vd(G×Kn)=n+Δ(G).(3)若χ′vd(Gi)=Δ(Gi),i=1,2,则χ′vd(G1×G2)=Δ(G1)+Δ(G2).     

图Sm*Cn的邻点可区别的边色数

定义图Sm*Cn为V（Sm*Cn）={ω,uij}i=1,2,…,m;j=1,2,…，n},E(Sm*Cn)={wuil}i=1,2,…m}∪uijuij 1}i=1,2,…,m;j=1,2,…，n-1}∪}uinuil|i=1,2,…，m}，文章给出了Sm*Cn的邻点可区别的边色数。     

若干图的广义字典积的点可区别边染色

在图G与不相交图序列hn=(Hi)i∈{0,1,…,n-1}的广义字典积G[hn]中,若Hi≌H,i=0,1,…,n-1,则将G[hn]记为G[H],其中G[H]是G与H的字典积。图G的点可区别边染色所需最少的颜色数称为G的点可区别边色数,记为χ'vd(G)。对任一满足χ'vd(G)=Δ(G)的图G,给出了参数χ'vd(G[hn])的两个上界,并证明这些上界是可达到的,其中hn=(Hi)i∈{0,1,…,n-1}中的每一个Hi均为m阶简单图。另外证明了:如果χ'vd(G)=Δ(G),χ'vd(H)=Δ(H)且Δ(G[H])=Δ(H[G]),则χ'vd(G[H])=χ'vd(H[G]),其中G与H分别为n阶与m阶的简单图。     

Wm与Pn(n≤3)联图的点可区别边色数

设G是简单图,图G的一个k-点可区别正常边染色f是指一个从E(G)到{1,2,…,k}的映射,且满足V u,v∈V(G),u≠v,有S(u)≠S(v),其中S(u)={f(uw)|uw ∈E(G)}.数min{k|G存在k-VDPEC染色}称为图G的点可区别正常边色数,记为χs(G),研究了WmVPn(n≤3)的点可区别边染色,给出了WmVPn(n≤3)的点可区别边色数.     

若干联图Pm∨Gn的邻点可区别E-全染色

记χat'e(G)为图G的邻点可区别E-全色数.若Pm是m阶的路,Sn是n+1阶的星,且nm≥2,则χate(Pm∨Sn)=4;若Pm是m阶的路,Fn是n+1阶的扇,且m≥2,n≥2,则χate(Pm∨Fn)=5;若Pm是m阶的路,Wn是n+1阶的轮,且m≥2,n≥3,如果n≡0(mod 2),则χate(Pm∨Wn)=5,如果n≡1(mod 2),则χate>(Pm∨Wn)=6;若Pm是m阶的路,Kn是n阶完全图,且n≥4,m≥2,则χate+(Pm∨Kn)=n+2.     

两类字典积图的Mycielski图的点可区别全染色

研究了当G为n阶轮,或扇,或星时,字典积图G[H]的Mycielski图M(G[H])的点可区别全染色,其中n≥6且H为m阶简单图.得到了以下结果:①若H为m阶完全图,则M(G[H])的点可区别全色数为2mn;②若H为m阶路,其中m≥4,则M(G[H])的点可区别全色数为2(n-1)m+6.     

完全图上的锥的D(2)-点可区别正常边染色

设G是顶点集合为V(G)={v_(0i)|i=1,2,…,p}的简单图,n是正整数,称M_n(G)为G上的锥(或广义Mycielski图),如果V(M_n(G)={v_(01),v_(02),…,v_(0p);v_(11),v_(12),…,v_(1p);…v_(n1),v_(n2),…,v_(np),w}) E(M_n(G))=E(G)∪{v_(ij)v_((i 1)k)|v_(0j)v_(0k)∈E(G),1≤j,k≤p,i=0,1,…,n-1}∪{v_(nj)w|1≤j≤p}.在这篇文章里,我们讨论了完全图上的锥的$D(2)$-点可区别的正常边染色,并给出了相应色数.     

图K_(2n)\E(F_5)(n≥13)的点可区别边染色

对简单图G(V,E),设f是从E(G)到{1,2,…,k}的映射,k为自然数,如果f满足:1)对任意的uv,uw∈E(G),v≠w,有f(uv)≠f(uw);2)对任意的u,v∈V(G),u≠v,有C(u)≠C(v).则称f为图G的k-点可区别边染色法,而最小的k被称为点可区别边色数(其中C(u)={f(uv)|uv∈E(G)}).研究了图K2n\E(F5)(n≥13)的点可区别边色数.     

若干强积图及合成图的邻点可区别一般边染色

讨论了若干满足某些条件的两个图的强积图以及合成图的邻点可区别一般边色数的若干结论, 并在此基础上得到了PnC2m+1, C2nFm, C2nW2m+1, PnFm, PnW2m+1, C2n+1C2m+1, Pn［C2m+1］, C2m+1［Pn］, C3［C2m+1］, C2m+1［C3］ 等图类的一般邻点可区别边色数。     

几类图的均匀邻点可区别全染色

 邻点可区别全染色是在正常全染色的定义下,使得任两相邻顶点的色集不同。设G（V,E）为一个简单图,f为G的一个k-邻点可区别全染色,若f满足||Vi∪Ei|－|Vj∪Ej||≤1（i≠j）,其中,Vi∪Ei={v|f（v）=i}∪{e|f（e）=i},记C（i）=Vi∪Ei,则称f为G的k-均匀邻点可区别全染色,简记为k-EAVDTC,并称χeat（G）=min{k|G存在k－均匀邻点可区别全染色}为G的均匀邻点可区别全染色数。本文给出了路、圈、风车图K t 3、图Dm,4和齿轮图■n的均匀邻点可区别全染色,以及它们的均匀邻点可区别全色数的确切值。     

图的一般邻点可区别色指标

给出了完全图Kn、路Pm与完全图Kn的Cartese积Pm×Kn、圈Cm与Kn的Cartese积Cm×Pn等图的一般邻点可区别色指标,并得到2维网格Mm,n2种颜色可染、2维环形网格TMm,n3种颜色可染等结论.     

关于图K2n+1-E(2 K2)的邻点可区别全色数

用K2n 1-E(2K2)表示2n 1阶的完全图删掉两条不相邻的边所得到的图,给出了图K2n 1-E(2K2)的邻点可区别全色数.     

W_m与P_n（n≤3）联图的点可区别边色数

设G是简单图,图G的一个k-点可区别正常边染色f是指一个从E（G）到{1,2,…,k}的映射,且满足u,v∈V（G）,u≠v,有S（u）≠S（v）,其中S（u）={f（uw）｜uw∈E（G）}.数min{k｜G存在k-VDPEC染色}称为图G的点可区别正常边色数,记为χs′（G）,研究了Wm∨Pn（n≤3）的点可区别边染色,给出了Wm∨Pn（n≤3）的点可区别边色数.     

直积图的邻点可区别全染色

设G,H为简单图.给出直积图G×H的邻点可区别全色数的一个上界,得到星、轮、扇分别与m阶路、圈的直积图的邻点可区别全色数.