无相交三角形平面图的邻点可区别边染色

图G的k-邻点可区别边染色是指G的一个正常k-边染色满足对任意相邻顶点u和v,与u关联的边所染颜色集合和与v关联的边所染颜色集合不同。使G有k-邻点可区别边染色的k的最小值称为G的邻点可区别边色数,记作χ'_a(G)。通过运用权转移方法研究了无相交三角形平面图的邻点可区别边色数,证明了若图G为无相交三角形平面图,则χ'_a(G)≤max{Δ(G)+2,10}。     

若干图的倍图的邻点可区别边(全)染色

设G是具有顶点集V(G)和边集E(G)的简单图。如果G的一正常边染色σ满足对任意uv∈E(G),有Cσ(u)≠Cσ(v),其中Cσ(u)为点u的关联边所染颜色构成的集合,则称σ为G的邻点可区别边染色。如果G的一正常全染色σ满足对任意uv∈E(G),有Sσ(u)≠Sσ(v),其中Sσ(u)表示点u及u的关联边所染颜色构成的集合,则称σ为G的邻点可区别全染色。图G的邻点可区别边(或全)染色所需的最少的颜色数,称为G的邻点可区别边(或全)色数,并记为χ’as(G)(或χat(G))。给出了图G的倍图D(G)的以上两个参数的上界,并对完全图与树,确定了它们的倍图的邻点可区别边色数与全色数的精确值。     

单圈图的邻和可区别边染色

图G的一个k-正常边染色,若满足任意两个相邻点的色集合中所有元素之和不同,则称该染色为图G的一个k-邻和可区别边染色。其中,k的最小值称为图G的邻和可区别边色数。运用分析法与数学归纳法,研究了单圈图的邻和可区别边色数。     

无限路的四类积图的邻和可区别全染色

图G的一个[k]-邻和可区别全染色是图G的一个[k]-全染色,其中f(v)表示点v以及所有和v相关联的边的颜色之和,满足对G的每一条边uv,都有f(u)≠f(v)成立.文章研究了无限路的四类积图的邻和可区别全染色,如无限路的笛卡尔积、直积、半强积与强积等,并得到了它们的邻和可区别全色数.     

子立方图的2-距离严格邻点可区别边染色

2-距离严格邻点可区别边染色是指图G有一个正常边染色，且任意2个距离为2的顶点的颜色集合互不包含.2-距离严格邻点可区别边色数是指使图G有一个2-距离严格邻点可区别边染色的最小颜色数值，记作χ^′_2-snd(G).采用反证法证明了：若图G是子立方图，则χ^′_2-snd(G)≤7.     

低度系列平行图的邻点可区别全染色

设G是阶数不小于2的简单连通图,G的k-正常全染色σ称为是邻点可区别的,如果对G的任意两个相邻顶点,它们的顶点及关联边的颜色构成的集合不同.满足上述条件的最小k称为是G的邻点可区别全色数.文中从系列平行图的结构性质出发,利用换色技巧、归纳法以及组合方法对最大度不大于7的系列平行图的邻点可区别全染色进行了研究.得到了当低度系列平行图中不含相邻最大度点时,其邻点可区别全色数是最大度加1,否则,其邻点可区别全色数的上界为最大度加3.     

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

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

P_m∨F_n及P_m∨W_n的邻点可区别I-全染色

图G的I-全染色是指对图G的顶点和边染色,使得任意两个相邻的点的颜色不同,任意两条相邻的边的颜色不同.图G的一个I-全染色称为是邻点可区别的,如果任意两个相邻顶点u,v的色集合C(u)≠C(v),这里C(u)={f(u)}∪{f(uv)|uv∈E(G)}.而图G的邻点可区别I-全染色中所用的最少色数称为图G的邻点可区别I-全色数.讨论路与扇的联图Pm∨Fn、路与轮联图Pm∨Wn的邻点可区别I-全染色问题,根据这类图的结构性质运用色构造法给出它们的邻点可区别I-全染色方法,从而有效地确定其邻点可区别I-全色数.     

中间图的邻点可区别全染色

设G是简单连通图,G的k-正常全染色f称为是邻点可区别的,如果对G的任意相邻的两顶点,其点的颜色及关联边的颜色构成的集合不同,称f为G的k-邻点可区别全染色,这样的k中最小者称为G的邻点可区别全色数,本文考虑了图的中间图的邻点可区别全色数,并确定了路、圈、星图和扇图的中间图的邻点可区别全色数.     

关于图rK2∨K8的邻点可区别全色数

对一个简单图G的一个正常全染色，来说，G的点v的色集合C（v）是与v关联的边的颜色以及点v的颜色所构成的集合．对此f，如果G的任意两个相邻顶点的色集合不同，则称，为G的邻点可区别全染色．对G进行邻点可区别全染色所需要的最少颜色数称为G的邻点可区别全色数．对图rK2∨K8的邻点可区别全色数进行了讨论．     

一类稀疏图的邻和可区别边色数

设φ为图G的正常k-边染色。 对任意v∈V(G),令f_φ(v)=∑_uv∈E(G)φ(uv)。 若对每条边uv∈E(G)都有f_φ(u)≠f_φ(v),则称φ为图G的k-邻和可区别边染色。 图G存在k-邻和可区别边染色的k的最小值称为G的邻和可区别边色数,记作 χ'Σ(G)。 确定了一类稀疏图的邻和可区别边色数,得到:若图G不含孤立边,Δ≥6且mad(G)≤5/2,则 χ'Σ(G)=Δ当且仅当G不含相邻最大度点。     

若干Mycielski图的邻点扩展和可区别全染色

讨论了Mycielski图M(Pn)、M(Cn)、M(Sn)、M(Fn)、M(Wn)的邻点扩展和可区别全染色问题.根据图形的结构特点,采用函数构造法,得到了这几类图的邻点扩展和可区别全色数,同时证明NESD猜想对上述5种My-cielski图是成立的.     

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

考虑路与路、 路与圈、 圈与圈三类联图的邻点全和可区别全染色问题, 通过构造边染色矩阵, 利用组合分析法和分类讨论的思想,  得到了路与路、 路与圈、 圈与圈三类联图的邻点全和可区别全色数的精确值.     

无K4-子式图的2-距离和可区别边染色

图G的一个正常边染色φ若满足:∠u,v∈V(G),且d_G(u,v)≤2都有f(u)≠f(v),其中f(u)=∑_uw∈E(G)φ(uw),则称φ为图G的2-距离和可区别边染色。运用反证法,结合构造染色函数法,研究了无K₄-子式图的2-距离和可区别边染色,确定了无K₄-子式图的2-距离和可区别边色数的一个上界。     

两圈之联、 路与圈的联及两路之联的邻点被扩展和可区别全染色#br#

构造两圈之联的邻点被扩展和可区别全染色, 并通过删边得到路与圈的联图及两路之联的最优邻点被扩展和可区别全染色. 结果表明, 这三类图的邻点被扩展和可区别全色数均等于2; NESDTC猜想对于两圈之联、 路与圈的联及两路之联成立.     

最大度为3或4的图的邻和可区别全染色

图 G 的一个正常[k]-全染色是一个映射：V∪E→｛1,2,…,k｝,使得 V∪E 中任意一对相邻或者相关联元素染不同颜色。用 f（v）表示点 v 及所有与其关联的边的颜色的加和,若对任意 uv∈E（G）,有 f（u）≠f（v）,则称该染色为图 G 的[k]-邻和可区别全染色。k 的最小值称作图 G 的邻和可区别全色数,记为 tndiΣ（G）。Pils＇niak 和Woz＇niak 提出猜想：对任意简单图 G,有 tndiΣ（G）≤Δ（G）＋3,其中Δ（G）为图 G 的最大度。图 G 的最大平均度,记为 mad（G）,是 G 的所有非空子图的平均度的最大值。运用组合零点定理和权转移方法,证明了若Δ（G）＝3且mad（G）＜125,或Δ（G）＝4且 mad（G）＜52,则 tndiΣ（G）≤Δ（G）＋2。     

K_n-｛v_1v_2,v_3v_4,v_5v_6,v_7v_8｝(n≥20,n≡0(mod2))的点可区别边色数

研究n阶完全图Kn(n≥20,n≡0(mod2))去掉4条独立边后的点可区别边染色,并给出了图Kn-{v1v2,v3v4,v5v6,v7v8}(n≥20,n≡0(mod2))的点可区别边色数。     

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

设G是简单图,f是从V(G)∪E(G)到{1,2,…,k]的一个映射.对每个u∈V(G),令C(u)={f(uv)|v∈V(G),uv∈E(G)].如果f是k-正常边染色,且对任意u,v∈V(G),有C(u)≠C(v),那么称f为图G的点可区别边染色(简称为k-VDEC).数x's(G)=min{k|G有k-VDEC}称为图G的点可区别边色数.本文通过应用概率方法,证明了对任意最大度△≥2的图G,x's(G)≤16△.     

超立方体的边可区别数

针对图(点)可区别数,提出了图的边可区别数,给出了n阶路Pn和n阶圈Cn的边可区别数;根据n维超立方体Hn及其p次幂Hpn的结构特性,对n维超立方体Hn和n维超立方体p(＞2)次幂Hpn的边可区别数进行了研究,得到了n维超立方体及其高次幂Hpn的边可区别数的一个上界.即,当n=2时,H2的边可区别数为3;当n≥3时,Hn的边可区别数为2;当n≥4,n≥p＞2时,Hpn的边可区别数小于等于3.     

关于哈林图的邻和可区别染色的注记

用三种树染色算法和组合分析法, 完成对哈林图的邻和可区别边染色、 邻和可区别全染色以及邻点全和可区别全染色, 并证明1-2-3 猜想 和1-2猜想对哈林图均成立. 结果表明, 哈林图的邻点全和可区别全色数不超过3.