图的邻点可区别VE-全色数的一个上界

根据图的邻点可区别VE-全染色的定义和性质,用概率方法研究了图的邻点可区别VE-全染色,并给出了图的邻点可区别VE-全色数的一个上界.如果δ≥7且△≥25,则有x_at^ue（G）≤7△,其中δ是图G的最小度,△是图G的最大度.     

某些中间图的邻点可区别E-全色数

设G（V,E）是简单连通图,T（G）为图G的所有顶点和边构成的集合,并设C是k-色集（k是正整数）,若T（G）到C的映射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的邻点可区别E-全染色（简记为k-AVDETC）,并称χ_（at）~e（G）=min{k｜图G有k-邻点可区别E-全染色}为G的邻点可区别E-全色数.图G的中间图M（G）就是在G的每一个边上插入一个新的顶点,再把G上相邻边上的新的顶点相联得到的.探讨了路、圈、扇、星及轮的中间图的邻点可区别E-全染色,并给出了这些中间图的邻点可区别E-全色数.     

若干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-全色数.     

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

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

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

Pm×Kn的邻点可区别全色数

设G是简单图．设f是一个从V(G)∪E(G)到{1,2,…,k}的映射．对每个v∈V(G),令C_f(v)={f(v)}∪{f(vw)|w∈V(G),vw∈E(G)}．如果f是k-正常全染色,且对任意u,v∈V(G),uv∈E(G),有C_f(u)≠C_f(v),那么称f为图G的邻点可区别全染色(简称为k-AVDTC)．数x_(at)(G)=min{k|G有k-AVDTC}称为图G的邻点可区别全色数．本文给出路P_m和完全图K_n的Cartesion积的邻点可区别全色数．     

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

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

轮与星的多重联图的邻点可区别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-全色数.     

$P_m\times K_n$的邻点可区别全色数

设 $G$ 是简单图. 设$f$是一个从$V(G)\cup E(G)$ 到$\{1, 2,\cdots, k\}$的映射. 对每个$v\in V(G)$, 令 $C_f (v)=\{f(v)\}\cup \{f(vw)|w\in V(G), vw\in E(G)\}$. 如果 $f$是$k$-正常全染色, 且对任意$u, v\in V(G), uv\in E(G)$, 有$C_f(u)\ne C_f(v)$, 那么称 $f$ 为图$G$的邻点可区别全染色(简称为$k$-AVDTC).数 $\chi_{at}(G)=\min\{k|G$ 有$k$-AVDTC\}称为图$G$的邻点可区别全色数.本文给出路$P_m$和完全图$K_n$ 的Cartesion积的邻点可区别全色数.     

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

设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的一个正常全染色被称为邻点可区别全染色,如果G中任意两个相邻点的色集合不同．本文用概率方法得到了邻点可区别全色数的一个上界．     

轮与路的多重联图的邻点可区别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的全染色是指对G的点和边都进行染色．称全染色为正常的如果没有相邻或关联元素染同一种颜色．简单图G=（VE）的正常全染色^称为它的邻点可区别全染色如果对任意两个相邻顶点u、v,有H（u）≠H（v）,其中H（u）={（u））U{^（uw）｜uw∈E（G））而H（v）={h（u）}U{h（vx）｜vx∈E（G））．G...     

M(C_n)和M(W_n)图的邻点可区别的Ⅰ-全色数

研究了M(C_n)和M(W_n)图的邻点可区别的I-一全染色.根据M(C_n)和M(W_n)图的构造特征,利用构造函数法,构造了一个从点边集V(G)∪E(G)到色集合{1,2,…,k)的函数,给出了一种染色方案,得到了它们的邻点可区别的I-全色数.     

圈的广义冠图的关联邻点可区别的全色数

研究了圈的广义冠图C_noC_m,C_n oF_m和C_no W_m的关联邻点可区别的全染色.根据圈的广义冠图C_noC_m,C_noF_m和C_noW_m的构造特征,利用构造函数法,构造了一个从集合V(G)∪E(G)到色集合{1,2,…,k}的函数,给出了一种染色方案,得到了它们的关联邻点可区别的全色数.     

高度平面图的邻点可区别全染色

图G 的邻点可区别全染色是G 的一个正常全染色, 使得每一对相邻顶点有不同的颜色集合. G的邻点可区别全色数χ_a′′ (G) 是使得G 有一个k- 邻点可区别全染色的最小颜色数k. 本文证明了: 若G 是满足最大度Δ(G) ≥ 11 的平面图, 则χ_a′′ (G) ≤ Δ(G) + 3.     

三类平方图的点边邻点可区别全色数

根据平方图的结构性质,用穷染,递推的方法,讨论了路,圈,扇的平方图的点边邻点可区别全染色,得到了相应的色数,即并给出了一种染色方案.     

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

两个简单图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的邻点可区别的边色数与全色数.给出了两个简单图的半强积的邻点可区别染色数的一个上界,并证明了该上界是可达的.然后,讨论了两个树的不同半强积具有相同邻点可区别染色数的充分必要条件.另外,确定了一类图与完全图的半强积的邻点可区别染色数的精确值.     

路、圈的广义Mycielski图的邻点可区别Ⅰ-全色数

图G的邻点可区别Ⅰ-全染色是一个满足相邻顶点色集合不同的Ⅰ-全染色,其中任意一点的色集合包含该顶点及其关联边所染的颜色.所需颜色的最小数称为邻点可区别Ⅰ-全色数,记作χ_atⁱ(G).研究了路和圈的广义Mycielski图的邻点可区别Ⅰ-全色数:对于阶数n≥2的路P_n,当n=2,3,4时,有χ_atⁱ(M(P_n))=n+1;否则,χ_atⁱ(M(P_n))=n.对于阶数n≥3的圈C_n,当n=3,4时,有χ_atⁱ(M(C_n))=5;否则,χ_atⁱ(M(C_n))=n.     

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

提出了一般邻点可区别全染色的新概念,给出了路、圈、星、树、二部图、轮、扇、完全图的一般邻点可区别全染色指标.并据此提出猜想.