S_n+W_n的邻点强可区别全色数

设G(V,E)是阶数不小于3的简单连通图,k是自然数,f是从V(G)∪E(G)到1,2,…,k的映射,满足:对任意的uv∈E(G),f(u)≠f(v),f(u)≠f(uv)≠f(v);对任意的uv,uw∈E(G)(v≠w),f(uv)≠f(uw);对任意的uv∈E(G),C(u)≠C(v),其中C(u)={f(u)}∪{f(v)uv∈E(G)}∪{f(uv)uv∈E(G)},则称f是图G的一个邻点强可区别的全染色法,简记作k-AVSDTC,且称χast(G)=min{k G的所有k-AVSDTC}为G的邻点强可区别的全色数.得到了星与轮联图的邻点强可区别的全色数.     

P_n~2和P_n~(n-1)的均匀邻强边色数

对阶至少为3的简单连通图G的k-正常边染色法f,若对任意uv∈E(G)有C(u)≠C(v),Ei-Ej 1,i,j=1,2,…,k.其中C(u)={f(uv)uv∈E(G)},Ei={uv f(uv)=i,uv∈E(G)},则称f为G的一k-均匀邻强边染色,简称k-EASEC.并称χe′as(G)=min{k k-EASEC of G}为G的均匀邻强边色数.给出了图Pn2与Pnn-1的均匀邻强边色数.     

Halin-图的邻强边染色

图G(V,E)的正常κ-边染色f叫做图G(V,E)的κ-邻强边染色当且仅当任意uv∈E(G)满足f[u]≠f[v],其中,f[u]={f(uw)|uw∈E(G)},称f是G的κ-临强边染色,简记为κ-ASEC.并且x′_as(G)=min{k|κ-ASEC of G}叫做G(V,E)的邻强边色数.本文研究了△(G)≥5的Halin-图的邻强边色数.     

联图Fn∨Pm的邻点可区别全染色

设G(V,E)是阶数至少为2的简单连通图,k是正整数,V∪E到{1,2,3,…k}的映射f满足:对任意uv,uw∈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),有G(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)．本文得到了联图Fn∨Pm的全色数．     

P2n和Pnn-1的均匀邻强边色数

对阶至少为3的简单连通图G的k-正常边染色法f,若对任意uv∈E(G)有C(u)≠C(v),||E|-|Ej||≤1,i,j=1,2,…,k.其中C(u)={f(uv)|uv∈E(G)},Ei={uv|f(uv)=i,uv∈E(G)},则称f为G的一k-均匀邻强边染色,简称k-EASEC.并称Xeas(G)=min{k|k-EASEC of G}为G的均匀邻强边色数.给出了图P2n与Pnn-1的均匀邻强边色数.     

△(G)=4的Halin-图的邻强边染色

图G(V,E)的一正常k-边染色f称为G(V,E)的一k-邻强边染色(简称k-ASEC)当且仅当任意uv∈E(G)满足f[u]≠f[v],其中f[u]={f(uw)|uw∈E(G)},并称Xas(G)=min{k|存在G的一k-ASEC}为G的邻强边色数.本文研究了△(G)=4的Halin-图的邻强边染色,得到了如下结果对△(G)=4的Halin-图有△(G)=4≤Xas(G)≤△(G)+1=5.     

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

G(V,E)是一个简单图,k是一个正整数,f是一个V(G)∪E(G)到{1,2,…,k}的映射.如果(V)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-全色数,其中C(u)={f(u)}∪ {f(uv)|uv∈E(G)}.     

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

设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)},研究了一些联图的邻点可区别-点边全染色法,得到了它们的色数.     

图 P2×Cn的均匀邻强边色数

对图G(V,E),一正常边染色f若满足(1)对(V)uv∈E(G),f[u]≠f[v],其中f[u]={f(uv)|uv∈E};(2)对任意i≠j,有||E|-|Ej||≤1,其中Ei={e| e∈E(G)且f(e)=i}.则称f为G(V,E)的一k-均匀邻强边染色,简称k-EASC,并且称Xcas(G)=min{k|存在G(V,E)的一k-EASC为G(V,E)的均匀邻强边色数.本文得到了图P2×Cn的均匀邻强边色数.     

1-树图的邻强边染色

图G的一k-正常边染色f若使得任意uv∈E(G)满足f[u]≠f[v],其中f[u]={f(uω)|uw∈E(G)},则称f为G的一k-邻强边染色,简称k-ASEC,并称χ_as(G)=min{k|存在G的一k-ASEC}为G的邻强边色数.本文提出了邻强边染色猜想:对2-连通图G(V,E)(G(V,E)≠C₅),有△(G)≤χ_as(G)≤△(G)+2,并研究了1-树图的邻强边染色,证明了对△(G)≥4的1-树图G有△(G)≤χ_as<     

图K_(2n)\E(K_(2,m))(n≥9,m≥3)的点可区别边染色

对简单图G(V,E),设f是从E(G)到{1,2,…,κ}的映射,κ为自然数,如果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的κ-点可区别边染色法,而最小的κ被称为点可区别边色数(其中C(u)={f(uv)|uv∈E(G)}).研究了图K_(2n)\E(K_(2,m))(n≥9,m≥3)的点可区别边色数.     

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

对简单图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)}.研究了图K_(2n)\E(F_4)(n≥12)的点可区别边色数.     

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

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

最大度不小于5的外平面图的邻强边染色

图G(V,E)的一k-正常边染色叫做k-邻强边染色当且仅当对任意uv∈E(G)有,f[u]≠f[v],其中f[u]={f(uw)|uw∈E(G)},f(uw)表示边uw的染色.并且x'as(G)=min{k|存在k-图G的邻强边染色}叫做图G的图的邻强边色数.本文证明了对最大度不小于5的外平面图有△≤x'as(G)≤△ 1,且x'as(G)=△ 1当且仅当存在相邻的最大度点.     

P_m×P_n的邻强均匀边色数

图G的一个k-正常着色满足相邻的点所关联的边的色集合不同,且任两色的边数之差不超过1称为G的k-邻强均匀边染色,图G邻强均匀边染色中最小的k称为图G的邻强均匀边色数.本文得到了P_m×P_n的邻强均匀边色数.     

若干笛卡尔积图的邻点可区别E-全染色

图G(V,E)的k是一个正整数,f是V(G)∪E(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-全色数.得到了Pm×Pn,Pm×Cn,Cm×Cn的邻点可区别E-全色数,其中C(u)={f(u)}∪{f(uv)uv∈E(G)}.