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

来源：大连理工大学学报杂志2017年第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的点可区别Ⅰ(Ⅵ)-全色数．利用组合分析法及构造具体染色的方法，讨论了圈与路的联图Cm∨Pn的点可区别Ⅰ(Ⅵ)-全染色问题，确定了这类图的点可区别Ⅰ(Ⅵ)-全色数，同时说明了VDITC猜想和VDVITC猜想对于这类图是成立的．

关键词：Ⅰ-全染色点可区别Ⅰ-全染色点可区别Ⅰ-全色数圈与路的联

基金资助：国家自然科学基金资助项目(61163037611630541126104661363060)；宁夏回族自治区百人计划资助项目.