完全图上的锥的D(2)-点可区别正常边染色

设G是顶点集合为V(G)={v_(0i)|i=1,2,…,p}的简单图,n是正整数,称M_n(G)为G上的锥(或广义Mycielski图),如果V(M_n(G)={v_(01),v_(02),…,v_(0p);v_(11),v_(12),…,v_(1p);…v_(n1),v_(n2),…,v_(np),w}) E(M_n(G))=E(G)∪{v_(ij)v_((i 1)k)|v_(0j)v_(0k)∈E(G),1≤j,k≤p,i=0,1,…,n-1}∪{v_(nj)w|1≤j≤p}.在这篇文章里,我们讨论了完全图上的锥的$D(2)$-点可区别的正常边染色,并给出了相应色数.     

路和圈上的锥的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)-点可区别正常边染色,并给出了相应的色数。     

一类联图的点可区别正常边染色

给出了图P3∨Kn与P4∨Kn的点可区别正常边染色的色数及染色方法,并讨论了图Pm∨Kn(m≥5),Cm∨Kn(m≥4)的点可区别正常边色数,给出了某些情况下它们的确切值.     

单圈图的D(2)-点可区别边染色

用数学归纳法、反证法及构造具体染色函数法,并结合Hall定理讨论单圈图的D(2)-点可区别边染色,并给出其确切的D(2)-点可区别边色数.     

图K_（3,3）∨K_t的点可区别正常边染色

图G的正常边染色称为是点可区别的,如果对G的任意两个不同的顶点u,v,与u关联的边的颜色构成的集合异于与v关联的边的颜色构成的集合。对图G进行点可区别正常边染色所需要的最少颜色数称为是G的点可区别正常边色数,记为χ＇s（G）。讨论了图K3,3∨Kt的点可区别正常边染色。     

图K3,3∨Kt 的点可区别正常边染色1

 图G的正常边染色称为是点可区别的, 如果对G的任意两个不同的顶点u,v, 与u关联的边的颜色构成的集合异于与v关联的边的颜色构成的集合。 对图G进行点可区别正常边染色所需要的最少颜色数称为是G的点可区别正常边色数, 记为χ′s(G)。讨论了图K_3,3∨Kt 的点可区别正常边染色。     

图mP2∪mCt（3≤t≤10）的点可区别正常边染色

图G的正常边染色称为是点可区别的,如果对G的任意两个不同的顶点u,v,与u关联的边的颜色构成的集合异于与v关联的边的颜色构成的集合.对图G进行点可区别正常边染色所需要的最少颜色数称为是G的点可区别正常边色数,记为χ′s(G).通过将路和圈填装到完全图,我们给出了mP2∪mCt的点可区别正常边色数的一个刻画,并利用递归染色的方式,得到了χ′s(mP2∪mCt)(3≤t≤10).     

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

首先,给出了完全图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的合成的点可区别正常边色数.     

-K3V Kn 的Smarandachely邻点可区别正常边染色

图的染色问题是图论研究的主要内容之一,起源于著名的"四色猜想"问题.图G的一个正常边染色f称为是Smarandachely邻点可区别的,如果对G中任何相邻的两个顶点u与v,与u关联的边的颜色的集合和与v关联的边的颇色构成的集合互不包含.对一个图G进行Smarandachely邻点可区别正常边染色所用的最少颜色数称为G的...     

C_m·P_n的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的无圈边着色是指图G的一个正常边着色且不含双色的圈.图G的无圈边色数是指图G的无圈边着色中所用色数的最小者,用x’a(G)表示;证明了如果G是一个D中的顶点不与3-面相关联,3-顶点不与D中的顶点相邻且Δ(G)≥6的平面图,则x’a(G)≤Δ(G)+1。     

Wm V C3的点可区别正常边色数

对于轮和圈的联图，给出了一种点可区别的边染色方法，并得到了其点可区别边色数．     

合成图的点可区别正常边色数

通过将图G和H的合成图G［H］分解成一个直积图G□H和一个二分图Z的边不交并的方法, 得到了χ′_s(G［H］)≤χ′_s(G□H)+χ′(Z),其中χ′_s(G)表示G的点可区别正常边色数.     

一类广义Petersen图的邻强边染色

研究了一类广义Petersen图G(n,k)的邻强边染色,构造性地证明了:若n≡0(mod3),k≡/0(mod3),则χ_(as)~′(G(n,k))=4.其中χa′s(G(n,k))表示G(n,k)的邻强边色数.     

K4-minor-free图的邻点可区别全染色

图G的一个正常全染色被称为邻点可区别全染色,如果G中任意两个相邻点的色集合不同.论文确定了k4-minor-free图的邻点可区别全色数.     

不含三角形的平面图的无圈边染色

图的无圈边染色是图的染色理论中的一个重要问题.2001年,Alon等猜想任意简单图G的无圈边色数都不超过Δ(G)+2,其中Δ(G)为图G的最大顶点度.为了深入研究该猜想对平面图是否成立,利用差值转移方法并结合最小反例图的一些结构性质,证明了:不包含三角形的平面图G,如果其最大顶点度不小于6,则其无圈边色数不超过Δ(G)+3.     

图多彩染色中的2度点删除问题

对整数r0,图G的一个r-多彩染色是一个从顶点集V(G)到数集{1,2,…,k}的映射c,使得:(C1)相邻点获得的颜色不同;(C2)︱c(N(v))︱≥min{N(v),r}(其中N(v)代表v的邻点集)。使图G有一个正常的(k,r)-染色的最小k值称为G的多彩色数χ_r(G)。本文主要研究在图G中删掉任意一个2度点后多彩色数的变化。