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

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

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

二部图中求正交于星的(g, f)-染色的一个多项式算法

令G是一个具有顶点集V(G)和边集 E(G)的二部图, 且令g和f是定义在 V(G)上的两个非负整数值函数,使得对每个顶点x∈V(G)都有g(x)≤f(x). G的一个(g,f)-染色是一个推广的边染色,它满足在每个顶点x每一种颜色至少出现g(x)次且至多出现f(x)次. 给出了求二部图中满足某些约束条件且具有最小颜色数的(g,f)-染色的一个多项式算法并证明了此结果是最好的可能.     

若干倍图的邻点可区别Ⅵ-全染色

图的一个边正常的全染色满足相邻点的色集合不同时被称为邻点可区别Ⅵ-全染色,把所用的最少颜色数称为邻点可区别Ⅵ-全色数,其中任意一点的色集合为点上与关联边所染的颜色构成的集合.应用构造邻点可区别Ⅵ-全染色函数法得到了路、圈、星和扇的倍图的邻点可区别Ⅵ-全色数,进一步验证图的邻点可区别Ⅵ-全染色猜想.     

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

路与星、扇、轮图的积图的邻点可区别Ⅰ-全染色

图G的Ⅰ-全染色是指若干种颜色对图G的顶点和边的一个分配,使得任意两个相邻顶点的颜色不同,任意两条相邻边的颜色不同.在图G的一个Ⅰ-全染色下,G的任意一个点的色集合是指该点的颜色以及与该点相关联的全体边的颜色构成的集合.图G的一个Ⅰ-全染色称为是邻点可区别的,如果任意两个相邻点的色集合不相等.对一个图G进行邻点可区别Ⅰ-全染色所用的最少颜色的数目称为图G的邻点可区别Ⅰ-全色数.应用构造具体染色的方法给出了路与星、扇、轮图的积图的邻点可区别Ⅰ-全色数     

关于联图K_(2,n)∨P_m的邻点可区别的全染色

一个全染色被称为邻点可区别的如果它满足对任意两个相邻点所关联的色集合不同.本文给出了联图K2,n∨Pm的邻点可区别的全色数并且证明了它满足邻点可区别的全染色猜想.     

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

路与星、扇、轮图的积图的邻点可区别I-全染色

图G的I-全染色是指若干种颜色对图G的顶点和边的一个分配,使得任意两个相邻顶点的颜色不同,任意两条相邻边的颜色不同.在图G的一个I-全染色下,G的任意一个点的色集合是指该点的颜色以及与该点相关联的全体边的颜色构成的集合.图G的一个I-全染色称为是邻点可区别的,如果任意两个相邻点的色集合不相等.对一个图G进行邻点可区别I-全染色所用的最少颜色的数目称为图G的邻点可区别I-全色数.应用构造具体染色的方法给出了路与星、扇、轮图的积图的邻点可区别I-全色数     

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

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

一些倍图的点可区别均匀边色数

如果图G的一个正常边染色满足任意两个不同点的关联边色集不同,且任意两种颜色所染边数目相差不超过1,则称为点可区别均匀边染色,其所用最少染色数称为点可区别均匀边色数.本文得到了星、扇和轮的倍图的点可区别均匀边色数.     

图M(S_n)和M(F_n)的点可区别均匀边色数

如果图G的一个正常边染色满足任意两个不同点的关联边色集不同,且任意两种颜色所染边数目相差不超过1,则称为点可区别均匀边染色(VDEEC),其所用最少染色数称为点可区别均匀边色数.本文用构造法研究了一些Mycielski图的点可区别均匀边染色,得到了星和扇的Mycielski图的点可区别均匀边色数,验证了它们满足点可区别均匀边染色猜想.     

关于积图点可区别边染色的若干结论

如果图G的一个正常边染色满足任意两个不同点的关联边色集不同, 则称为点可区别边染色(VDEC), 其所用最少颜色数称为点可区别边色数. 利用构造法给出了积图点可区别边染色的一个结论, 得到了关于积图点可区别边色数的若干结果, 并且给出25个具体积图的点可区别边色数, 验证了它们满足点可区别边染色猜想(VDECC).     

高度平面图的邻点可区别全染色

图G 的邻点可区别全染色是G 的一个正常全染色, 使得每一对相邻顶点有不同的颜色集合. G的邻点可区别全色数χ_a′′ (G) 是使得G 有一个k- 邻点可区别全染色的最小颜色数k. 本文证明了: 若G 是满足最大度Δ(G) ≥ 11 的平面图, 则χ_a′′ (G) ≤ Δ(G) + 3.     

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

图G的一个正常全染色被称为邻点可区别全染色,如果G中任意两个相邻点的色集合不同．本文用概率方法得到了邻点可区别全色数的一个上界．     

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

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

一些分裂图的点可区别全染色

图G的一个k-正常染色被称为点可区别全染色指任意两点的点及其关联边所染色集合不同.研究了一些分裂图K_(2n+1)\E(K_m)(n≥4,m≥3)的点可区别全色数.     

图P_m□K_n的邻点可区别Ⅰ-全染色

应用构造具体染色的方法给出了m阶路和n阶完全图K_n的Cartesian积图的令β点可区别I-全染色得到了图P_m囗K_n的邻点可区别I-全色数.     

图的邻点可区别全染色的渐近性质

图G的一个正常全染色被称为邻点可区别全染色,如果G中任意两个相邻点的色集合不同,其所用的最少颜色数称为邻点可区别全色数.张忠辅老师猜想:对于|V(G)|≥3的连通图G,其邻点可区别全色数最多不超过△(G)+3.用概率方法证明了对简单图G,△≥14,有χ_(at)(G)≤△+C,其中C≥10~(26)+1.     

推广的Mycielski图和类推广的Mycielski图的(邻点可区别的)全染色

Mycielski图是在1955年由Mycielski首先提出的,推广的Mycielski图是在2003年由Peter Che Bor Lam,林文松等给出的Mycielski图的一个自然推广,且研究了它的圆色数.目前关于推广的Mycielski图性质以及它们在点色数,分数色数,圆色数等方面已有许多研究.本文定义了推广的Mycielski图的另一推广称为类推广的Mycielski图,且探讨了推广的Mycielski图和类推广的Mycielski图在全染色、邻点可区别全染色方面与原基础图的关系,从而也得到了它们满足全染色猜想和邻点可区别全染色猜想及它们达到全色数和邻点可区别的全色数的下界的一些充分条件.