苗 婷 婷,王 治 文,陈 祥 恩*

(1.西北师范大学 数学与统计学院， 甘肃 兰州 730070；2.宁夏大学 数学计算机科学学院， 宁夏 银川 750021 )

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

苗 婷 婷1,王 治 文2,陈 祥 恩*1

(1.西北师范大学 数学与统计学院， 甘肃 兰州 730070；2.宁夏大学 数学计算机科学学院， 宁夏 银川 750021 )

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

Ⅰ-全染色；点可区别Ⅰ-全染色；点可区别Ⅰ-全色数；圈与路的联

0 引 言

点可区别正常边染色、点可区别一般边染色以及点可区别正常全染色分别在文献[1-2]、[3-5]和[6-7]中被研究．文献[8]讨论了两类点可区别的未必正常的全染色：点可区别Ⅰ-全染色和点可区别Ⅵ-全染色．本文在文献[8]的基础上讨论圈与路的联图Cm∨Pn的点可区别Ⅰ-全染色和点可区……