距离限制下的点可区别全色数的一个上界

图G的-个正常全染色被称作D(β)-点可区别全染色,如果G中距离不超过β的任意两点有不同的色集,其中,每个点的色集由该点和其邻边的颜色所组成.本文得到了图G的-个D(β)-点可区别全色数的新上界.     

一类正则循环图的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相似文献   

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

设G是简单图,若图G的全染色f满足:1)(V)uv,vw∈E(G),有f(uv)≠f(vw);2)(V)uv∈E(G),u≠v,有f(u)≠f(v);3)(V)u,v∈V(G),0＜d(u,v)≤β,有S(u)≠S(v),这里色集合S(u)={f(u)}∪{f(uv) |uv∈E(G)}.则称f是图G的一个D(β)-点可区别Ⅰ-全染色.若f只满足条件1)和3),则称f是图G的一个D(β)-点可区别Ⅵ-全染色.研究了当β=1,2时一类正则循环图与圈的Cartesian积图的D(β)-点可区别Ⅵ-全色数和D(β)-点可区别Ⅰ-全色数,并讨论了正则图的D(β)-点可区别Ⅵ-全色数和D(β)-点可区别Ⅰ-全色数的上界.     

图与其Mycielski图关联色数的关系

本文证明了对n阶图G,若其最大度△(G)的2倍不等于n,且G的关联色数等于△(G) 1,则M(G)的关联色数为△(M(G)) 1．同时还研究了树和完全二部图的Mycielski图的关联色数．文末提出了M(G)的关联色数猜想,其中M(G)为图G的Mycielski图．     

C_m·S_n的D(2)-点可区别边色数

对阶数不小于3的连通图G(V,E),设α,β为正整数,令映射f:Ef{1,2,…,α},若u,v∈V(G),1≤d(u,v)≤β,有C(u)≠C(v),则称f为G的一个α-D(β)-点可区别的边染色,简记为α-D(β)-VDPEC,对一个图进行α-D(β)-点可区别的边染色,所需的最少的颜色数称为图G的D(β)-点可区别的边色数,记为χ′β-vd(G),其中d(u,v)表示两个点u,v之间的最短距离.得到了Cm.Sn的D(2)-点可区别边色数.     

单圈图的伴随多项式的极小根（英文）

引入伴随多项式是为了从补图的角度研究色多形式,图的伴随多项式的极小根可用于判定色等价图.β（G）表示图G的伴随多项式的极小根.n表示n个顶点的单圈图的集合.分别确定了具有max{β（G）｜G∈Ωn}和min{β（G）｜G∈Ωn}的所有单圈图.     

5-桥图F(2,a,a,b,c)的色等价刻画

设P(G，λ)是图G关于变量λ的色多项式，P(G，λ)=P(H，λ)，称G和H色等价，由连接两个顶点的S条内部不交的路组成的图叫S-桥图。本讨论了5-桥图F(2,a,a,b,c)(c≥b≥a 1，a≥2)的色性，完整刻画了这类图的色等价图。     

Pkn(k≡2(mod3))的D(2)-点可区别全染色

图的D(β)-点可区别全染色就是指图G的一个正常全染色且使得距离不大于β的任意两点有不同的色集合.讨论了幂图P_n~k当k≡2(mod3)时的D(2)-的点可区别全染色,并且根据P_n~2与C_n~2图的结构关系获得C_n~2的邻点可区别的全染色数.     

若干完全三部图的色唯一性

用P(G,λ)表示图G的色多项式.若对任意图H,当P(H,λ)=P(G,λ)时都有H和G同构,则称图G是色唯一的.给出了以下结果:m≥2且k≥0时,完全三部图K(m,m,m+k)是色唯一的;m≥2且m+1>k≥0时,完全三部图K(m,m+1,m+k)是色唯一的.     

粘合运算对图的控制参数的影响

简单图G的粘合运算G_(uv)指的是重合G的两个顶点{u,v}并且去掉重边和环所得到简单图的运算．本文考虑了粘合运算对图的4个控制参数γ(G),Γ(G),β(G),i(G)的影响．刻画了图G_(uv)与图G的控制参数γ(G),Γ(G),γ(G),i(G)之间的关系．及给出γ(G_(uv))=γ(G)-1和β(G_(uv)=β(G)-1的充要条件．