关于圈的不交并的点可区别全染色的若干结果

发布时间：2020-06-22 02:38

【摘要】：设f是对简单图G的顶点和边的一个染色,称f是G =(V,E)的(正常)全染色,如果满足下面的3个条件:(v)任意两个相邻的顶点被分配不同的颜色;(e)任意两条相邻边被分配不同的颜色;(i)每条边与其关联的顶点被分配不同的颜色.上述3个条件分别叫做V-条件,E-条件和I-条件.图G的一般全染色是指k种颜色1,2,…,kk对图G的全体顶点和全体边的一个分配.设f是图G的一个一般全染色,称f是G的V-全染色,如果满足E-条件和I-条件.设G是一个简单图,f为G的一个全染色[或一个V-全染色],x为G的一个顶点,将在f下x的颜色以及与x关联的边的颜色所构成的集合(非多重集)记为Cf(x)或C(x),即C(x)= {f(xm)}|xu∈E}(?){f(x)},并称之为点x的色集合.若对图G的任意两个不同的顶点u,v,有C(u)≠C(v),则f称为图G的点可区别全染色[或点可区别V-全染色].对图G进行点可区别全染色[或点可区别V-全染色]所需要的最少颜色的数目称为G的点可区别全色数[或点可区别V-全色数],记为xvt(G)[或xvtv(G)].利用色集合事先分配法,本文分别讨论了m个长为6,7,8,9的圈的点不交的并mC6,mC7,mC8,m(C9的点可区别全染色,并且确定了它们的点可区别全色数。
【学位授予单位】：西北师范大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：O157.5

【参考文献】