|
1.
|
图的邻点可区别全染色算法
|
|
|
|
|
|
|
李敬文 贾西贝 董威 李小慧 闫光辉《山东大学学报(理学版)》,2015年第2期
|
|
|
在图 G 的一个正常全染色下，G 中任意一点 v 的色集合是指点 v 的色以及与 v 关联的全体边的色所构成的集合。图 G 的邻点可区别全染色就是图 G 的正常全染色且使相邻点的色集合不同，其所用最少颜色数称为图 G的邻点可区别全色数。设计了一种启发式的邻点可区别全染色算法，该算法根据邻点可区别全染色的约束规则，确定四个子目标函数和一个总目标函数，然后借助染色矩阵及色补集合逐步迭代交换，每次迭代交换后判断目标函数值，当目标函数值满足要求时染色成功。实验结果表明，该算法可以得到图的邻点可区别全色数，并且算法的时间复杂度不超过 O（n3）。
|
|
2.
|
关于图rK2∨K8的邻点可区别全色数 被引次数：1
|
|
|
|
|
|
|
陈祥恩《兰州大学学报(自然科学版)》,2007年第43卷第5期
|
|
|
对一个简单图G的一个正常全染色，来说，G的点v的色集合C（v）是与v关联的边的颜色以及点v的颜色所构成的集合．对此f，如果G的任意两个相邻顶点的色集合不同，则称，为G的邻点可区别全染色．对G进行邻点可区别全染色所需要的最少颜色数称为G的邻点可区别全色数．对图rK2∨K8的邻点可区别全色数进行了讨论．
|
|
3.
|
关于图rK2 ∨ Ks的邻点可区别全色数
|
|
|
|
|
|
|
陈祥恩《兰州大学学报(自然科学版)》,2007年第43卷第5期
|
|
|
对一个简单图G的一个正常全染色f来说,G的点v的色集合C(V)是与v关联的边的颜色以及点v的颜色所构成的集合.对此f,如果G的任意两个相邻顶点的色集合不同,则称f为G的邻点可区别全染色.对G进行邻点可区别全染色所需要的最少颜色数称为G的邻点可区别全色数.对图rK2∨K8的邻点可区别全色数进行了讨论.
|
|
4.
|
P_m∨F_n及P_m∨W_n的邻点可区别I-全染色
|
|
|
|
|
|
|
王继顺《兰州理工大学学报》,2014年第40卷第4期
|
|
|
图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-全色数.
|
|
5.
|
冠图Cm·Fn、Cm·Sn与Cm·Wn的邻点可区别Ⅰ-全染色
|
|
|
|
|
|
|
杨随义 杨晓亚 何万生《兰州理工大学学报》,2011年第37卷第6期
|
|
|
图G的Ⅰ-全染色是指若干种颜色对图G的顶点和边的一个分配,使得任意两个相邻的点的颜色不同,任意两条相邻的边的颜色不同.在图G的一个Ⅰ-全染色下,G的任意一个点的色集合是指该点的颜色以及与该点相关联的全体边的颜色构成的集合.图G的一个Ⅰ-全染色称为是邻点可区别的,如果任意两个相邻点的色集合不相等.对一个图G进行邻点可区别Ⅰ-全染色所用的最少颜色的数目称为图G的邻点可区别Ⅰ-全色数.应用构造具体染色的方法给出冠图Cm·Fn、Cm·Sn及Cm·Wn的邻点可区别Ⅰ-全色数.
|
|
6.
|
两类3-正则图的邻点可区别I-全染色
|
|
|
|
|
|
|
杨随义 杨晓亚 唐保祥 何万生《山西大学学报(自然科学版)》,2012年第4期
|
|
|
图G的I-全染色是指若干种颜色对图G的顶点和边的一个分配,使得任意两个相邻的点的颜色不同,任意两条相邻的边的颜色不同.在图G的一个I-全染色下,G的任意一个点的色集合是指该点的颜色以及与该点相关联的全体边的颜色构成的集合.图G的一个I-全染色称为是邻点可区别的,如果任意两个相邻点的色集合不相等.对一个图G进行邻点可区别I-全染色所用的最少颜色的数目称为图G的邻点可区别I-全色数.本文给出了两类3-正则图的邻点可区别I-全色数.
|
|
7.
|
中间图的邻点可区别全染色 被引次数：1
|
|
|
|
|
|
|
陈纲 赵科军《漳州师范学院学报》,2009年第22卷第2期
|
|
|
设G是简单连通图,G的k-正常全染色f称为是邻点可区别的,如果对G的任意相邻的两顶点,其点的颜色及关联边的颜色构成的集合不同,称f为G的k-邻点可区别全染色,这样的k中最小者称为G的邻点可区别全色数,本文考虑了图的中间图的邻点可区别全色数,并确定了路、圈、星图和扇图的中间图的邻点可区别全色数.
|
|
8.
|
几类有趣图的邻点可区别全染色 被引次数：1
|
|
|
|
|
|
|
董海燕 孙磊《山东科学》,2006年第19卷第2期
|
|
|
在正常全染色的定义下,使得任两相邻顶点的色集不同,这就是邻点可区别全染色.顶点v的色集是v的颜色其与及v关联的所有边的颜色.我们给出了几类有趣图的邻点可区别全色数.
|
|
9.
|
关于一类图的邻点可区别全染色
|
|
|
|
|
|
|
胡凤凤 刘家保《重庆工商大学学报(自然科学版)》,2015年第2期
|
|
|
图G的一个正常全染色f称为是邻点可区别的,如果G中任何相邻点及其关联边的颜色集合不同;对一个图G进行邻点可区别的正常全染色所用最少颜色数称为G的邻点可区别全色数,记为χat(G);给出了一类特殊图类的邻点可区别全色数.
|
|
10.
|
圈与路联图点可区别Ⅰ-全染色和点可区别Ⅵ-全染色
|
|
|
|
|
|
|
苗婷婷 王治文 陈祥恩《大连理工大学学报》,2017年第57卷第4期
|
|
|
一个图 G 的Ⅰ-全染色是指若干种颜色对图 G 的全体顶点及边的一个分配使得任意两个相邻点及任意两条相邻边被分配到不同颜色．图 G 的Ⅵ-全染色是指若干种颜色对图 G 的全体顶点及边的一个分配使得任意两条相邻边被分配到不同颜色．对图 G 的一个Ⅰ(Ⅵ)-全染色及图 G 的任意一个顶点 x，用C(x)表示顶点x的颜色及x 的关联边的颜色构成的集合(非多重集)．如果 f 是图 G 的使用 k 种颜色的一个Ⅰ(Ⅵ)-全染色，并且 u，v∈V(G)，u≠v，有C(u)≠C(v)，则称f为图G的k -点可区别Ⅰ(Ⅵ)-全染色，或 k -VDITC(VDVITC)．图 G 的点可区别Ⅰ(Ⅵ)-全染色所需最少颜色数目，称为图 G 的点可区别Ⅰ(Ⅵ)-全色数．利用组合分析法及构造具体染色的方法，讨论了圈与路的联图 C m∨P n 的点可区别Ⅰ(Ⅵ)-全染色问题，确定了这类图的点可区别Ⅰ(Ⅵ)-全色数，同时说明了VDITC猜想和VDVITC猜想对于这类图是成立的．
|
|
11.
|
平面图的邻点可区别全染色
|
|
|
|
|
|
|
李泽鹏 王治文 陈祥恩《山东大学学报(理学版)》,2011年第46卷第4期
|
|
|
图G的一个正常全染色f称为是邻点可区别的,如果G中任何相邻点的点及其关联边的颜色集合不同.对一个图G进行邻点可区别的正常全染色所用最少颜色数称为G的邻点可区别全色数,记为xat(G).证明了xat(G)≤△(G)+2对任意的△(G)≥11且围长至少为4的平面图G成立.
|
|
12.
|
几类笛卡尔积图的邻点可区别全染色
|
|
|
|
|
|
|
王倩 田双亮《苏州科技学院学报(自然科学版)》,2010年第27卷第4期
|
|
|
图G的邻点可区别全染色是指G的任意相邻顶点具有不同色集的全染色,所需要的最少颜色数称为G的邻点可区别全色数.文章得到了圈与星、轮、扇的笛卡尔积图的邻点可区别全色数.
|
|
13.
|
若干图的倍图的邻点可区别边(全)染色
|
|
|
|
|
|
|
何雪 田双亮《山东大学学报(理学版)》,2015年第4期
|
|
|
设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)的以上两个参数的上界,并对完全图与树,确定了它们的倍图的邻点可区别边色数与全色数的精确值。
|
|
14.
|
-K3V Kn 的Smarandachely邻点可区别正常边染色
|
|
|
|
|
|
|
刘顺琴 陈祥恩《兰州理工大学学报》,2011年第37卷第1期
|
|
|
图的染色问题是图论研究的主要内容之一,起源于著名的四色猜想问题.图G的一个正常边染色f称为是Smarandachely邻点可区别的,如果对G中任何相邻的两个顶点u与v,与u关联的边的颜色的集合和与v关联的边的颜色构成的集合互不包含.对一个图G进行Smarandachely邻点可区别正常边染色所用的最少颜色数称为G的Smarandachely邻点可区别正常边色数,简称为G的SA-边色数,记为χ′sa(G).讨论K3∨Kn的SA-边色数,得到相应的结果.
|
|
15.
|
中间图的邻点可区别全染色
|
|
|
|
|
|
|
陈纲 ;赵科军《漳州师院学报》,2009年第2期
|
|
|
设G是简单连通图，G的庀．正常全染色f称为是邻点可区别的，如果对G的任意相邻的两顶点，其点的颜色及关联边的颜色构成的集合不同，称f为G的k-邻点可区别全染色．这样的后中最小者称为G的邻点可区别全色数．本文考虑了图的中间图的邻点可区别全色数，并确定了路、圈、星图和扇图的中间图的邻点可区别全色数．
|
|
16.
|
C2m×Cn图邻点可区别的边染色
|
|
|
|
|
|
|
刘海涛 刘永平 谢继国 张效贤 张锐《甘肃科学学报》,2007年第19卷第2期
|
|
|
设G是阶数不小于3的简单连通图 ,G的k-正常边染色称为是邻点可区别的,如果对G任意相邻两顶点关联边的颜色集合不同 ,则k中最小者称为是G的邻点可区别的边色数.证明了C2m×Cn的邻点可区别的边色数是5.
|
|
17.
|
Pm∨Pn的邻点可区别全染色 被引次数：13
|
|
|
|
|
|
|
陈祥恩 张忠辅《西北师范大学学报》,2005年第41卷第1期
|
|
|
设G是阶数不小于2的简单连通图,G的k 正常全染色f称为是邻点可区别的,如果对G的任意相邻的两顶 点,其点的颜色及关联边的颜色构成的集合不同.这样的k中最小者称为是G的邻点可区别全色数.得到了两条路的 联图的邻点可区别全色数.
|
|
18.
|
低度系列平行图的邻点可区别全染色
|
|
|
|
|
|
|
王淑栋 任淑红《自然科学进展》,2007年第17卷第6期
|
|
|
设G是阶数不小于2的简单连通图,G的k-正常全染色σ称为是邻点可区别的,如果对G的任意两个相邻顶点,它们的顶点及关联边的颜色构成的集合不同.满足上述条件的最小k称为是G的邻点可区别全色数.文中从系列平行图的结构性质出发,利用换色技巧、归纳法以及组合方法对最大度不大于7的系列平行图的邻点可区别全染色进行了研究.得到了当低度系列平行图中不含相邻最大度点时,其邻点可区别全色数是最大度加1,否则,其邻点可区别全色数的上界为最大度加3.
|
|
19.
|
完全二部图K3,n（n≥18）的点可区别E-全染色
|
|
|
|
|
|
|
李世玲 陈祥恩 王治文《山东大学学报(理学版)》,2016年第4期
|
|
|
G是一个简单图,G的一个E-全染色f是指使相邻点着不同色且每条关联边与它的端点着以不同的色的全染色。设f为G的一个E-全染色。对任意点x∈V(G),用C(x)表示在f下点x的色以及与x关联的边的颜色所构成的集合。若u,v∈V(G),u≠v,有C(u)≠C(v),则f称为是图G的点可区别的E-全染色,简称为VDET染色。图G的VDET染色所用颜色数目的最小值称为图G的点可区别E-全色数或简称为VDET色数,记为χevt(G)。讨论并给出了完全二部图K3,n(n≥18)的点可区别E-全色数。
|
|
20.
|
关于邻点可区别全染色的几个新结果 被引次数：5
|
|
|
|
|
|
|
董海燕 孙磊 孙艳丽《广西师范大学学报(自然科学版)》,2005年第23卷第3期
|
|
|
邻点可区别全染色是在正常全染色的定义下,使得任两相邻顶点的色集不同.顶点ν的色集是ν的颜色及其与ν关联的所有边的颜色.我们给出了几类特殊图的邻点可区别全色数.
|
