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

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