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

如果图G的一个正常全染色满足相邻点的色集合不同,且任意两种颜色所染的元素的数目之差的绝对值不超过1,则称为邻点可区别均匀全染色(AVDETC),其所用的最少颜色数称为邻点可区别均匀全色数。本文研究了路、圈、星、扇的Mycielski图的邻点可区别均匀全染色,利用构造法和匹配法给出了它们的邻点可区别全色数的确切值,验证了它们满足邻点可区别均匀全染色猜想(AVDETCC)。     

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

给出了一个简单图G的k重Mycielski图Mk（G）（其中k为正整数）的邻点可区别全色数的上界,得到了圈、星、轮、扇的k重Mycielski图的邻点可区别全色数.     

关于Mycielski图的点可区别均匀全染色

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

若干Mycielski图的邻点可区别V-全染色简

研究了路、圈、扇、轮的Mycielski图的邻点可区别的V-全染色.根据Mycielski图的构造特征,利用构造函数法,构造了一个从点边集V(G)∪E(G)到色集合{1,2,…,k}的函数,给出了一种染色方案,得到了路、圈、扇、轮的Mycielski图的邻点可区别的V-全色数.?更多还原     

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

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

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

研究一些倍图的邻点可区别均匀全染色(AVDETC), 利用构造法和匹配法给出了偶阶完全图、 偶阶圈、 路、 星和轮的倍图的邻点可区别均匀全色数, 并验证了它们满足邻点可区别均匀全染色猜想(AVDETCC).     

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

 邻点可区别全染色是在正常全染色的定义下,使得任两相邻顶点的色集不同。设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为正整数)的点可区别全色数的上界.     

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

对图G的一个邻点可区别的I-全染色f,若f还满足任意两种颜色所染元素(点和边)个数最大相差为1,则称f为图G的一个邻点可区别的I-均匀全染色.对图G进行邻点可区别的I-均匀全染色所需最少的颜色数称为图G的邻点可区别I-均匀全色数.研究了图D(C_n),D(S_n),D(F_n),D(W_n)的邻点可区别I-均匀全染色,通过函数构造法,得到了其的邻点可区别I-均匀全色数,并验证了其满足猜想:χ■(G)≤Δ(G)+2.     

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

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

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

研究若干联图的邻点可区别全染色,证明了:当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.     

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

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

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

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

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

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

若干广义Petersen图的邻点可区别全染色

研究了若干广义Petersen图G(n,r)的邻点可区别全染色。 构造性地证明了:若n≡0(mod 4),r0(mod 4)或n≡0(mod 5),r0(mod 5),则G(n,r)的邻点可区别全色数为5。     

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

为了进一步研究图的邻点全和可区别全染色问题,该文根据倍图的结构性,通过穷染法和染色算法,得到了路、圈、星、扇、轮、完全二部图以及树的倍图的邻点全和可区别全色数的精确值.     

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

利用函数构造法和数学归纳法,考虑图P_m∨S_n,F_m∨W_n和W_m∨W_n的邻点可区别I-全染色,给出了它们邻点可区别I-全色数.     

直积图的邻点可区别全染色

设G,H为简单图.给出直积图G×H的邻点可区别全色数的一个上界,得到星、轮、扇分别与m阶路、圈的直积图的邻点可区别全色数.     

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

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

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

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