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

图G的D(β)-点可区别正常边染色是指G的一个正常边染色f使得对任意两点u,v∈V(G),0相似文献   

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

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

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

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的邻点可区别的全染色数.     

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

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

一类正则循环图的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(β)-点可区别Ⅰ-全色数的上界.     

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

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

图K_(3,4)∨K_t的点可区别正常边染色

设f是图G的一个正常边染色.对任意x∈V(G),令S(x)表示与点x相关联的边的颜色所构成的集合.若对任意u,v∈V(G),u≠v,有S(u)≠S(v),则称f是图G的一个点可区别正常边染色.对一个图G进行点可区别正常边染色所需的最少的颜色的数目称为G的点可区别正常边色数,记为χ_s'(G).讨论了图K_(3,4)∨K_t的点可区别正常边染色及其色数,利用正多边形的对称性构造染色以及组合分析的方法,确定了图K_(3,4)∨K_t的点可区别正常边色数,得到了当t是大于等于2的偶数以及t是奇数且3≤t≤25时,χ_s'(K_(3,4)∨K_t)=t+7;当t是奇数且t≥27时,χ_s'(K_(3,4)∨K_t)=t+8.     

关于图K_(2n)-E(C_4)的点可区别边色数

图G的一个k-正常边染色f被称为点可区别边染色是指任何两点的点及其关联边的色集合不同,所用最小的正整数k被称为G的点可区别边色数,记为x′_(vd)(G).用K_(2n)-E(C_4)表示2n阶完全图删去其中一条4阶路的边后得到的图,文中得到了K_(2n)-E(_4)的点可区别边色数.     

图的2-强边色数的上界

本文研究了图的2-强边色数的上界. 利用图染色的概率方法中的一般局部引理, 得到了3 ≤Δ ≤ 730时,χ''_s(G,2) ≤ 2Δ + 1, 推广了参考文献[11,12]中的结果     

图的2-强边色数的上界

本文研究了图的2-强边色数的上界.利用图染色的概率方法中的一般局部引理,得到了3≤Δ≤730时,χs(G,2)≤2Δ+1,推广了参考文献[11,12]中的结果     

路的字典积的邻和可区别边染色

图G的正常[k]-边染色σ是指颜色集合为[k]={1,2,…,k}的G的一个正常边染色.用w_σ（x）表示顶点x关联边的颜色之和,即w_σ（x）=∑_e∋x σ（e）,并称w_σ（x）关于σ的权.图G的k-邻和可区别边染色是指相邻顶点具有不同权的正常[k]-边染色,最小的k值称为G的邻和可区别边色数,记为χ'_∑（G）.现得到了路P_n与简单连通图H的字典积P_n[H]的邻和可区别边色数的精确值,其中H分别为正则第一类图、路、完全图的补图.     

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

图的边对策着色和边对策色数

本文介绍了边对策着色,讨论了图G的边对策着色的性质.对几种特殊图类进行了讨论,分别确定链图,圈图及与圈有关的图,扇图,Petersen图的边对策色数.     

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

Vertex‐distinguishing edge colorings of graphs

We consider lower bounds on the the vertex‐distinguishing edge chromatic number of graphs and prove that these are compatible with a conjecture of Burris and Schelp 8 . We also find upper bounds on this number for certain regular graphs G of low degree and hence verify the conjecture for a reasonably large class of such graphs. © 2002 Wiley Periodicals, Inc. J Graph Theory 42: 95–109, 2003     

Edge‐face chromatic number and edge chromatic number of simple plane graphs

Given a simple plane graph G, an edge‐face k‐coloring of G is a function ? : E(G) ∪ F(G) → {1,…,k} such that, for any two adjacent or incident elements a, b ∈ E(G) ∪ F(G), ?(a) ≠ ?(b). Let χ_e(G), χ_ef(G), and Δ(G) denote the edge chromatic number, the edge‐face chromatic number, and the maximum degree of G, respectively. In this paper, we prove that χ_ef(G) = χ_e(G) = Δ(G) for any 2‐connected simple plane graph G with Δ (G) ≥ 24. © 2005 Wiley Periodicals, Inc. J Graph Theory