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

通过构造以色集合和空集为元素的矩阵,利用色集合事先分配法及构造具体染色的方法,解决了图mC15的最优点可区别Ⅰ-全染色及最优点可区别Ⅵ-全染色问题,得到了图mC15的点可区别Ⅰ-全色数和点可区别Ⅵ-全色数.结果表明,点可区别Ⅰ-全染色猜想和点可区别Ⅵ-全染色猜想对图mC15成立.     

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

通过构造以色集合和空集为元素的矩阵,利用色集合事先分配法及具体的染色方案,给出图mC8的最优点可区别Ⅰ-全染色和最优点可区别Ⅵ-全染色,进而确定图mC8的点可区别Ⅰ-全色数和点可区别Ⅵ-全色数.结果表明,VDITC猜想和VDVITC猜想对图mC8成立.     

圈与路联图点可区别Ⅰ-全染色和点可区别Ⅵ-全染色

一个图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猜想对于这类图是成立的.     

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

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

若干联图的邻点可区别全染色

研究若干联图的邻点可区别全染色,证明了:当n≥3时,χat(Kn∨Cn)=χat(Kn∨Pn)=2n+1;当n≥4时,χat(Kn∨Wn?1)=χat(Kn∨Fn?1)=χat(Kn∨Sn?1)=2n+1.     

若干Mycielski图邻点可区别Ⅰ-均匀全染色

图G的一个邻点可区别Ⅰ-均匀全染色是指对图G的邻点可区别的一个Ⅰ-全染色f,若f还满足||T_i|-|T_j||≤1(i≠j),其中T_i=V_i∪E_i={v|v∈V(G),f(v)=i}∪{e|e∈E(G),f(e)=i},则称f为图G的一个邻点可区别Ⅰ-均匀全染色,而图G的邻点可区别Ⅰ-均匀全染色中所用的最少颜色数称为图G的邻点可区别Ⅰ-均匀全色数.通过函数构造法,得到了M(Pn)、M(Cn)、M(Sn)的邻点可区别Ⅰ-均匀全色数,并且满足猜想.     

m个长为14的圈的不交并的点可区别Ⅰ-全染色

通过构造以色集合和空集为元素的矩阵,利用色集合事先分配法及构造具体染色的方法,证明mC₁₄的最优点可区别Ⅰ-全染色及最优点可区别Ⅵ-全染色,确定图mC₁₄的点可区别Ⅰ-全色数和点可区别Ⅵ-全色数。结论表明,点可区别Ⅰ-全染色猜想和点可区别Ⅵ-全染色猜想对图mC₁₄成立。     

完全图的倍图的邻点可区别全染色

讨论D(Kn)的邻点可区别全染色问题,给出并证明D(Kn)的邻点可区别全色数χat(D(Kn))=2n.     

几类图的均匀邻点可区别全染色

 邻点可区别全染色是在正常全染色的定义下,使得任两相邻顶点的色集不同。设G（V,E）为一个简单图,f为G的一个k-邻点可区别全染色,若f满足||Vi∪Ei|－|Vj∪Ej||≤1（i≠j）,其中,Vi∪Ei={v|f（v）=i}∪{e|f（e）=i},记C（i）=Vi∪Ei,则称f为G的k-均匀邻点可区别全染色,简记为k-EAVDTC,并称χeat（G）=min{k|G存在k－均匀邻点可区别全染色}为G的均匀邻点可区别全染色数。本文给出了路、圈、风车图K t 3、图Dm,4和齿轮图■n的均匀邻点可区别全染色,以及它们的均匀邻点可区别全色数的确切值。     

多重Mycielski图的点可区别全染色

给出了最小度至少是2的图G的k重Mycielski图M~k(G)(其中k为正整数)的点可区别全色数的上界.     

立方图的邻点可区别全染色及一般邻点可区别全染色

根据圈的立方图的性质,利用穷染、置换的方法,研究了立方图C3n的邻点可区别全染色及一般邻点可区别全染色.通过设计染色方案,给出了立方图C3n的邻点可区别全色数及一般邻点可区别全色数指标,且色数均可取到下界.     

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

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

关于一类图的邻点可区别全染色

图G的一个正常全染色f称为是邻点可区别的,如果G中任何相邻点及其关联边的颜色集合不同;对一个图G进行邻点可区别的正常全染色所用最少颜色数称为G的邻点可区别全色数,记为χat(G);给出了一类特殊图类的邻点可区别全色数.     

mK的点可区别全染色mK的点可区别全染色

 利用色集事先分配法, 借助于矩阵构造具体染色及递归法的方法, 研究图的点可区别全染色问题, 给出了m个K4的点不交的并mK4的点可区别全色数χvt(mK4)的确切值, 即“如果k-14<4m≤k4, m≥2, k≥6, 则χvt(mK4)=k”. 验证了VDTC猜想对mK4成立.     

若干补倍图的点可区别全染色

一个图的正常全染色被称为点可区别的即对任意两个不同点所染色颜色与该点相关联元素所染颜色构成的色集合不同。其中所用的最少颜色数称为点可区别全色数。给出了若干补倍图的点可区别全色数。     

图K（r，2m）的邻点可区别全染色

在等完全r-部图全染色的研究中,首先确定了每部有2个点的完全r-部图的全色数;然后利用已得到的结果进一步研究每部有n个点的完全r-部图的全色数．采用上述思路研究了等完全卜部图的邻点可区别全染色,利用图分解的方法给出了每部有2个点的完全r-部图的邻点可区别全色数;并给出了每部有偶数个点的等完全r-部图的邻点可区别全色数．     

mC3∨nC3和mC4∨nC4点可区别Ⅰ-全染色及Ⅵ-全染色

设f为简单图G的一个一般全染色(即若干种颜色对图G的全部顶点及边的一个分配),如果任意两个相邻点染以不同颜色且任意两条相邻边染以不同的颜色,则称为图G的Ⅰ-全染色;如果任意两条相邻边染以不同的颜色,则称为图G的Ⅵ-全染色.用C(x)表示在f下点x的颜色以及与x关联的边的色所构成的集合(非多重集).对图G的一个Ⅰ-全染色(分别地,Ⅵ-全染色)f,一旦?u,v∈V(G),u≠v,就有C(u)≠C(v),则f称为图G的点可区别Ⅰ-全染色(或点可区别Ⅵ-全染色),简称为VDIT染色(分别地,VDVIT染色).令χ~Ⅰ_(vt)(G)=min{k|G存在k-VDIT染色},称χ~Ⅰ_(vt)(G)为图G的点可区别Ⅰ-全色数.令χ~Ⅵ_(vt)(G)=min{k|G存在k-VDVIT染色},称χ~Ⅵ_(vt)(G)为图G的点可区别Ⅵ-全色数.利用构造具体染色的方法,讨论了联图mC_3∨nC_3和mC_4∨nC_4的点可区别Ⅰ-全染色和点可区别Ⅵ-全染色,并给出了联图mC_3∨nC_3和mC_4∨nC_4的点可区别Ⅰ-全色数和点可区别Ⅵ-全色数.     

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

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

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

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

若干图的倍图的点可区别均匀全染色

研究了一些倍图的点可区别均匀全染色(VDETC),利用构造法给出了星、扇和轮的倍图的点可区别均匀全色数,并验证了它们满足点可区别均匀全染色猜想(VDETCC).