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

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

两类3-正则图的邻点可区别I-全染色

图G的I-全染色是指若干种颜色对图G的顶点和边的一个分配,使得任意两个相邻的点的颜色不同,任意两条相邻的边的颜色不同.在图G的一个I-全染色下,G的任意一个点的色集合是指该点的颜色以及与该点相关联的全体边的颜色构成的集合.图G的一个I-全染色称为是邻点可区别的,如果任意两个相邻点的色集合不相等.对一个图G进行邻点可区别I-全染色所用的最少颜色的数目称为图G的邻点可区别I-全色数.本文给出了两类3-正则图的邻点可区别I-全色数.     

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

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

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

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

图的邻点可区别全染色算法

在图 G 的一个正常全染色下,G 中任意一点 v 的色集合是指点 v 的色以及与 v 关联的全体边的色所构成的集合。图 G 的邻点可区别全染色就是图 G 的正常全染色且使相邻点的色集合不同,其所用最少颜色数称为图 G的邻点可区别全色数。设计了一种启发式的邻点可区别全染色算法,该算法根据邻点可区别全染色的约束规则,确定四个子目标函数和一个总目标函数,然后借助染色矩阵及色补集合逐步迭代交换,每次迭代交换后判断目标函数值,当目标函数值满足要求时染色成功。实验结果表明,该算法可以得到图的邻点可区别全色数,并且算法的时间复杂度不超过 O（n3）。     

冠图Cm·Fn、Cm·Sn与Cm·Wn的邻点可区别Ⅰ-全染色

图G的Ⅰ-全染色是指若干种颜色对图G的顶点和边的一个分配,使得任意两个相邻的点的颜色不同,任意两条相邻的边的颜色不同.在图G的一个Ⅰ-全染色下,G的任意一个点的色集合是指该点的颜色以及与该点相关联的全体边的颜色构成的集合.图G的一个Ⅰ-全染色称为是邻点可区别的,如果任意两个相邻点的色集合不相等.对一个图G进行邻点可区别...     

点可区别全色数的一个界

图G的一个正常全染色被称作点可区别全染色,如果G中任意两个点的色集合不同,其中每个点的色集合包含该点及其关联边的颜色。在点可区别全色数界(χvt(G)≤|V(G)|+2)的基础上,应用概率的方法得到了阶数为n,且无孤立边的简单图G的点可区别全色数的一个较小上界。     

K5,5,p的点可区别的IE-全染色（p≥2 028）

图G的IE-全染色f是指对?u,v∈V（G）,使得f（u）≠f（v）的一个一般全染色,其中u,v相邻,V（G）是图G的顶点集.设f是图G的IE-全染色,图G的一个顶点x在f下的色集合C（x）是指由x及x的关联边的颜色所构成的集合（非多重集）.若图G的任意两个不同顶点的色集合不同,则f称为图G的点可区别的IE-全染色（简记为VDIETC）.利用色集合事先分配法、构造染色法及反证法探讨了完全三部图K_5,5,p（p≥2028）的点可区别的IE-全染色问题,确定了K_5,5,p（p≥2028）的点可区别的IE-全色数.     

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-全色数.     

冠图C_n■C_m的邻点可区别均匀E-全染色

讨论了冠图C_n■C_m的邻点可区别均匀E-全染色,并得到了它们的邻点可区别均匀E-全色数.对简单图G,如果图G存在一个染色法f,使得任意两个相邻的顶点染不同的颜色;任意一条边与其关联的点染不同的颜色;任意两个相邻的点的色集合不相同,并且任意两色所染元素的数目之差不超过1,则称该染色法为G的邻点可区别均匀E-全染色,其所用最少颜色数称为该图的邻点可区别均匀E-全色数.     

幂图的邻点可区别全色数和邻点可区别-VE全色数

根据路的幂图Pkn的结构性质,用穷染、递推的方法,讨论了Pkn的邻点可区别全染色和邻点可区别-VE全染色,得到了相应的色数,并给出了一种染色方案.     

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

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

K1,1,p,K1,2,p的点可区别的IE-全染色及一般全染色

以完全三部图K_1,1,p,K_1,2,p为例, 利用色集事先分配法、 构造染色法、 反证法, 讨论完全三部图K_1,1,p,K_1,2,p的点可区别IE-全染色及点可区别一般全染色问题, 确定了K_1,1,p,K_1,2,p的点可区别IE-全色数及点可区别一般全色数.     

(P~2)_n和(P~3)_n的D(3)-点可区别全染色

图的染色问题是图论研究的经典领域,在网络结构和实际生活中都有着广泛的应用,随着计算机和通讯、电力网络的日益发展,染色问题成为近年来图论研究的热点.图的D(β)-点可区别全染色又是染色问题中的难点.通过分类讨论、归纳探究,在图的点边集合与色集合间构造了一种一一对应关系.讨论了幂图Pkn(k=2,3)的点可区别全染色,使得距离不大于3(D(3))的任意2点都有不同的色集合,得到幂图Pkn(k=2,3)的D(3)-点可区别全染色数.     

mC7的点可区别Ⅰ-全染色和Ⅵ-全染色

利用色集合事先分配法及具体的染色给出了mC7的最优点可区别Ⅰ-全染色以及最优点可区别Ⅵ-全染色,进而确定了图mC7的点可区别Ⅰ-全色数及点可区别Ⅵ-全色数。结论表明VDITC猜想和VDVITC猜想对图mC7成立。     

SmVPn的邻点可区别全色数

设G的阶数不小于2的简单连通图。G的k-正常全染色称为是邻点可区别的，如果对G的任意相邻的两顶点，其点的颜色及关联边的颜色构成的集合不同。这样的k中最小者称为G的邻点可区别全色数。本文主要是给出了星图和路的联图的邻点可区别全色数，并提出了一猜想。     

Sm∨Pn的邻点可区别全色数

设G的阶数不小于2的简单连通图.G的k-正常全染色称为是邻点可区别的,如果对G的任意相邻的两顶点,其点的颜色及关联边的颜色构成的集合不同.这样的k中最小者称为G的邻点可区别全色数.本文主要是给出了星图和路的联图的邻点可区别全色数,并提出了一猜想.     

完全二部图K5,n的点可区别IE全染色

设G是简单图, 图G的一个k 点可区别IE 全染色(简记为k VDIET染色) f是指一个从V(G)∪E(G)到｛1,2,…,k｝的映射, 且满足:uv∈E(G),有f(u)≠f(v);u,v∈V(G), u≠v, 有C(u)≠C(v), 其中C(u)=｛f(u)｝∪｛f(uv)|uv∈E(G)｝。 数min｛k|G有一个k VDIET染色｝称为图G的点可区别IE 全色数,记为χievt(G)。本文给出了完全二部图K5,n(n≥6)的点可区别IE 全色数。     

mC_7的点可区别全染色

考虑m个长为7的圈点不交的并mC7的点可区别全染色问题.通过构造以色集合为元素的矩阵,利用色集合事先分配法及递归法确定染色,得出了mC_7的点可区别全色数的确切值.结果表明VDTC猜想对图mC_7成立.