几类笛卡尔乘积图的邻点全和可区别全染色

设f:V(G)∪E(G)→[k]是图G的一个非正常的k-全染色,令权重 φ(x)=f(x)+∑x∈e f(e)+∑y∈N(x)f(y),其中,N(x)={y∈V(G)|xy∈E(G)}对任意的边uv∈E(G),如果有φ(u)≠φ(v)成立,则称f为图G的一个邻点全和可区别非正常k-全染色.图G的邻点全和可区别非正常全染...     

图在约束条件下的邻点可区别全染色

设f:V(G)∪E(G)→{1,2,…,k}是简单图G的一个正常k-全染色.令C(f,u)={f(e):e∈Ne(u)},C[f,u]=C(f,u)∪{f(u)},C2[f,u]=C(f,u)∪{f(x):x∈N(u)}∪{f(u)}. N(u)表示顶点u的邻集,Ne(u)表示与顶点u的相关联的边集合.令C[f; x]={C(f,x); C[f,x]; C2[f,x]},对任意的边xy∈E(G),C[f; x]≠C[f; y]表示C(f,x)≠C(f,y),C[f,x]≠C[f,y],C2[f,x]≠C2[f,y]同时成立.对任意的边xy∈E(G),如果有C[f; x]≠C[f; y]成立,则称f是图G的一个k-(3)-邻点可区别全染色(简记为k-(3)-AVDTC).图G的(3)-邻点可区别全染色中所需最少的颜色数叫做G的(3)-邻点可区别全色数,记为(″3) as(G).文章研究(2,2)-递归极大平面图的(3)-邻点可区别全染色,并确定此类图的(3)-邻点可区别全色数.此外,提出了简单图的(3)-邻点可区别全染色猜想.     

C_m×K_n的邻点可区别全染色

设G(V,E)是阶数至少为2的简单连通图,k是正整数,V∪E到{1,2,3,…,k}的映射f满足:对任意uv,vw∈E(G),u≠w,有f(uv)≠f(vw);对任意uv∈E(G),有f(u)≠f(v),f(u)≠f(uv),f(v)≠f(uv);那么称f为G的k-正常全染色,若f还满足对任意uv∈E(G),有C(u)≠C(v),其中C(u)={f(u)}∪{f(uv)|uv∈E(G),v∈V(G)},那么称f为G的k-邻点可区别的全染色(简记为k-AVDTC),称min{k|G有k-邻点可区别的全染色}为G的邻点可区别的全色数,记作Xat(G).本文得到了圈Cm和完全图Kn的笛卡尔积图Cm×Kn邻点可区别的全色数.     

Cm×Kn的邻点可区别全染色

设G（V，E）是阶数至少为2的简单连通图，k是正整数，V∪E到{1，2，3，…，k）的映射f满足：对任意uυ，υw∈E（G），u≠w，有f（uv）≠f（υw）；对任意uυ∈E（G），有，（u）≠，（υ），f（u）≠f（uυ），f（υ）≠f（uυ）；那么称f为G的k-正常全染色，若，还满足对任意uυ∈E（G），有C（u）≠C（υ），其中C（u）={（u））∪{f（uυ）｜uυ∈E（G），υ∈V（G）），那么称，为G的k-邻点可区别的全染色（简记为k-AVDTC），称min{k｜G有k-邻点可区别的全染色）为G的邻点可区别的全色数，记作xat（G）．本文得到了圈Cm和完全图Kn的笛卡尔积图Cm×Kn邻点可区别的全色数．     

点可区别全色数的一个上界

设G是简单图，f是从V（G）UE（G）到{1,2，…，k）的一个映射．对每个u∈y（G），令c（u）={f（u）}v∈V（G）,uv∈ E（G）}．如果，是k-正常全染色，且对任意u，v∈V（G）（u≠v），有c（u）≠c（v），那么称f为图G的k-点可区别全染色（简记为k-VDTC）．数χvt（G）=min{k｜G-有k—VDTC}称为图G的点可区别全色数．通过应用概率方法，证明了对任意最大度A≥2的图G，χvt（G）≤32（△＋1）．     

Cm×Kn的邻点可区别全染色

设G（V，E）是阶数至少为2的简单连通图，k是正整数，V∪E到{1，2，3，…，k）的映射f满足：对任意uυ，υw∈E（G），u≠w，有f（uv）≠f（υw）；对任意uυ∈E（G），有，（u）≠，（υ），f（u）≠f（uυ），f（υ）≠f（uυ）；那么称f为G的k-正常全染色，若，还满足对任意uυ∈E（G），有C（u）≠C（υ），其中C（u）={（u））∪{f（uυ）｜uυ∈E（G），υ∈V（G）），那么称，为G的k-邻点可区别的全染色（简记为k-AVDTC），称min{k｜G有k-邻点可区别的全染色）为G的邻点可区别的全色数，记作xat（G）．本文得到了圈Cm和完全图Kn的笛卡尔积图Cm×Kn邻点可区别的全色数．     

关于几类特殊图的Mycielski图的邻点可区别全色数

设G是一个简单图,f是一个从V(G)∪ E(G)到{1,2,…,k}的映射.对每个v∈V(G),令Cf(v)={f(v)}∪{f(vw)|w∈V(G),vw∈E(G)}.如果f是G的正常全染色且u,v∈V(G),一旦uv∈E(G),就有Cf(u)≠Cf(v),那么称f为G的邻点可区别全染色(简称为k-AVDTC).设xat(G)=min{k|G存在k-AVDTC},则称xat(G)为G的邻点可区别全色数.给出了路、圈、完全图、完全二分图、星、扇和轮的Mycielski图的邻点可区别全色数.     

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

 邻点可区别全染色是在正常全染色的定义下,使得任两相邻顶点的色集不同。设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的均匀邻点可区别全染色,以及它们的均匀邻点可区别全色数的确切值。     

关于若干倍图的关联邻点可区别全染色

对简单图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的一个关联邻点可区别全染色,所需的最少颜色数称为图G的关联邻点可区别全色数.给出了路、圈、星、扇、轮倍图的关联邻点可区别全色数.     

Mycielski图的一般邻点可区别全色数

设图G(V,E)是阶数至少为2的简单连通图,k是正整数.从V∪E到{1,2,…,k}的映射f称为图G的一般邻点可区别全染色(简记k-GAVDTC),如果对任意2个相邻顶点u≠v的色集合C(u)≠C(v),其中C(u)={f(u)}∪{f(uv)|uv E(G)},并称χgat(G)=min{k|G有k-GAVDTC}为图G一般邻点可区别全色数.综合运用构造法、调整法及概率法讨论了路、圈、扇、星、轮和完全二部图的Mycielski图的一般邻点可区别全染色,给出了其确切的一般邻点可区别全色数.     

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

G(V,E)是一个简单图,k是一个正整数,f是V(G)∪E(G)到{1,2,…,k}的一个映射.如果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的邻点可区别E-全染色,称最小的数k为图G的邻点可区别E-全色数.得到路和圈的联图的邻点可区别E-全色数.     

部分图笛卡儿积图的邻点可区别VE-全染色

对简单图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-全染色,且称最小的数k为图G的邻点可区别VE-全色数.讨论一些图的图笛卡儿积图的邻点可区别VE-全染色,得到它们的邻点可区别VE-全色数.     

中间图的邻点可区别全染色

设G是简单连通图,G的k-正常全染色f称为是邻点可区别的,如果对G的任意相邻的两顶点,其点的颜色及关联边的颜色构成的集合不同,称f为G的k-邻点可区别全染色,这样的k中最小者称为G的邻点可区别全色数,本文考虑了图的中间图的邻点可区别全色数,并确定了路、圈、星图和扇图的中间图的邻点可区别全色数.     

P_m∨S_n的点可区别全色数

设G是简单图,f 是从V(G)∪E(G) 到{1,2,…,k}的一个映射.对每个u∈V(G),令C(u)={f(u)}∪{f(uv)|v∈V(G),uv∈E(G)}.如果f是k-正常全染色,且对任意u,v∈V(G),有C(u)≠C(v),那么称f为图G的点可区别全染色(简称为k-VDTC).数χv t(G)=min{k|G有k-VDTC}称为图G的点可区别全色数.给出m阶路Pm和n 1阶星Sn的联图的点可区别全色数.     

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

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

奇圈、偶圈与轮的多重联图的邻点可区别E-全染色(英文)

G(V,E)是一个简单图,k是一个正整数,f是一个V(G)∪E(G)到{1,2,…,k}的映射,如果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的邻点可区别E-全染色,称最小的数k为图G的邻点可区别E-全色数,给出了奇圈、偶圈与轮的多重联图的邻点可区别E-全色数.     

完全二部图K5，n的点可区别IE-全染色

设G是简单图,图G的一个k-点可区别IE-全染色（简记为k-VDIET染色）f是指一个从V（G）∪E（G）到{1,2,…,k}的映射,且满足：A↓uv∈E（G）,有f（u）≠f（v）;A↓u,v∈V（G）,u≠v,有C（u）≠C（v）,其中C（u）={f（u）}∪{f（uv）｜uv∈E（G）}。数min{k}G有一个k-VDIET染色}称为图G的点可区别IE-全色数,记为χut^ie（G）。本文给出了完全二部图K5,n（n≥6）的点可区别IE-全色数。     

图的点强全染色

图G(V,E)的正常k—全染色f叫做G(V,E)的k—点强全染色,当且仅当对任意的w∈V(G),N[w]中元素染不同颜色,其中N[w]={x|wx∈E(G)}∪{w}.并称XvTs(G)=min{k|存在G的k—点强全染色}为图G(V,E)的点强全色数.本文研究了K4-minor free图和外平面图的点强全色数.     

三星的最优的一般点可区别全染色

设G为简单图.所谓G的k-一般全染色f是指从V(G)∪E(G)到{1,2,…,k}的一个映射.设f为G的一个一般全染色,x为G的一个顶点,令C(x)={f(xu)xu∈E}∪{f(x)},称之为顶点x在f下的色集合.设f是G的一个一般全染色,若对图G的任意两个不同的顶点u,v,有C(u)≠C(v),则f称为图G的一般点可区别全染色(GVDTC).本文给出了三星的最优的一般点可区别全染色.     

一类稀疏图的邻和可区别边色数

设φ为图G的正常k-边染色。 对任意v∈V(G),令f_φ(v)=∑_uv∈E(G)φ(uv)。 若对每条边uv∈E(G)都有f_φ(u)≠f_φ(v),则称φ为图G的k-邻和可区别边染色。 图G存在k-邻和可区别边染色的k的最小值称为G的邻和可区别边色数,记作 χ'Σ(G)。 确定了一类稀疏图的邻和可区别边色数,得到:若图G不含孤立边,Δ≥6且mad(G)≤5/2,则 χ'Σ(G)=Δ当且仅当G不含相邻最大度点。