Cm·Pn的D(3)-点可区别边色数

对阶数不小于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)表示两个点之间的最短距离.得到Cm.Pn的D(3)-点可区别边色数.

图的点可区别星边色数的一个上界(英文)

图G的点可区别星边边色数，记为X＇vds（G），是图G的点可区别星边染色所用色的最小数目．得到了一些特殊图的星边染色，并证明了若图G是一个最小度不小于5，且顶点数不超过△7的图时，X＇vds（G）≤14△2其中△是图G的最大度．

图的D(2)-点可区别边色数的一个上界

用图的概率方法中的赋权局部引理得到最大度不小于5的图的D(2)-点可区别边色数的一个上界是4(2d4-d3-4d2+5d-1)d-1,这里d是图G的最大度.

星和扇上的锥的D(2)-点可区别正常边染色

设G是顶点集合为V(G)={v0i|i=1,2,…,p}的简单图,n是正整数,称Mn(G)为G上的锥(或广义Mycielski图),如果V(Mn(G))={v01,v02,…,v0p;v11,v12,…,v1p;…,vn1,vn2,…,vnp,w},E(Mn(G))=E(G)∪{vijv(i+1)k|v0jv0k∈E(G),1≤j,k≤p,i=0,1,…,n-1}∪{vnjw|1≤j≤p}.在这篇文章里,我们讨论了星和扇上的锥的D(2)-点可区别的正常边染色,并给出了相应色数.

完全图和星的合成的点可区别正常边染色(英文)

首先,给出了完全图K_p和星S_q的合成的点可区别正常边色数的一个上界:当p≥2,q≥4时,上界是pq+1.再利用正多边形的对称性以及组合分析的方法来构造染色,分别得到了当p=2,q≥4;p≥3,q=4;p是偶数且p≥4,q=5;pq是奇数且p≥3,q≥5时,完全图K_p和星S_q的合成的点可区别正常边色数.

路和圈上的锥的D(2)-点可区别正常边染色

设G是顶点集合为V(G)={v0i|i=1,2,…,p}的简单图,n是正整数,称Mn(G)为G上的锥(或广义My-cielski图),如果V(Mn(G))={v01,v02,…,v0p;v11,v12,…,v1p;…;vn1,vn2,…,vnp,w},E(Mn(G))=E(G)∪{vijv(i+1)k|v0jv0k∈E(G),1≤j,k≤p,i=0,1,…,n-1}∪{vnjw|1≤j≤p}。讨论了路和圈上的锥的D(2)-点可区别正常边染色,并给出了相应的色数。

图的D(2)-点可区别一般边染色

引入了图的D(β)-点可区别一般边染色,并对β=2的情形做了讨论,得到了路,圈,星,双星,扇,轮的D(2)-点可区别一般边色数,对于2距离色数等于3及4的图的D(2)-点可区别一般边色数做了探讨,特别研究了具有稳定2距离4着色的图的D(2)-点可区别一般边染色.文中提出了一个相关猜想和一个公开问题.

C_m·P_n的距离不大于β的任意两点可区别的边染色

给出了图Cm.Pn的距离不大于β的任意两点可区别的边色数,并研究了某些情况下Cm.Pn的点可区别的边色数.

路和圈的距离不大于3和4的点可区别边染色

对阶数不小于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间的距离.研究路和圈的距离不大于3和4的点可区别边染色,得到路和圈的距离不大于3和4的点可区别的边色数.

图的D(2)点可区别星边色数的一个上界

提出了图的D(β)点可区别星边染色及D(β)点可区别星边色数的概念,并用Lovasz局部引理证明了在β=2时,若G=(V,E)是一个最小度为δ(G)>3的简单无向图,则X_(2-vds)(G)≤24△2/3]。

Cm·Sn的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)-点可区别边色数.

D(2)-点可区别正常边色数的一个上界

图G的D(β)-点可区别正常边染色是指G的一个正常边染色f使得对任意两点u,v∈V(G),0<d(u,u)≤β,有S(u)≠S(v),这里S(x)表示与图G的顶点x关联的边的颜色所构成的集合,称为点x的色集合.主要研究图的D(2)-点可区别正常边染色.利用一般局部引理,得到了当δ≥max{(3^(1/2)/2)Δ:(2(3^(43/2)/3}时,G的D(2)-点可区别正常边色数不超过Δ+5.

图的邻点可区别星边色数的一个上界

提出了图的邻点可区别星边染色及邻点可区别星边色数χ'ass(G)的概念,并用Lovász局部引理证明了若G=(V,E)是一个最小度为δ(G)≥3的简单无向图,则χ'ass(G)≤「32Δ32?。

图的距离不大于β的任意两点可区别的边染色

本文提出了图的距离不大于β的任意两点可区别的边染色,即D(β)-点可区别的边染色(简记为D(β)-VDPEC)．并得到了一些特殊图类,如圈、完全图、完全二部图、扇、轮、树以及一些联图的D(β)-点可区别的边色数,文后提出了相关的猜想．