赵亚迪, 陈祥恩

(西北师范大学 数学与统计学院, 兰州 730070)

1 引言与预备知识

目前, 关于图的点可区别的正常边染色与点可区别的一般边染色研究已有很多结果[1-6]. 图G的一个k-全染色是指用k种颜色{1,2,…,k}对图G的全体顶点及边的一个分配, 对图G的每个顶点y,Cf(y)指在f下点y的颜色及与y关联的全体边的颜色构成的集合(非多重集), 称为y的色集合. 设f是图G的一个正常全染色, 如果对∀u,v∈V,u≠v, 有C(u)≠C(v), 则称f是图G的点可区别全染色(VDTC)[7-8].

本文所研究的图均为有限的无向简单图, 考虑点可区别的一类未必正常的全染色. 设f为图G的k-全染色, 若任意两个相邻顶点在f下的色不相同, 且任意两条相邻边在f下的色也不相同, 则该染色f称为图G的Ⅰ-全染色. 如果在f下图G的任意相邻两条边均染不同颜色, 则称f为Ⅵ-全染色. 易知Ⅰ-全染色必为Ⅵ-全染色[9-10]. 设f为图G的Ⅰ-全染色(Ⅵ-全染色), 若图G任意两个顶点的色集合均不相同, 则称f是点可区别的. 分配k种颜色的点可区别的Ⅰ-全染色简记为k-VDITC(k-点可区别的Ⅵ-全染色简记为k-VDVITC).

显然图的VDITC一定是图的VDVITC, 因此本文只需讨论图的最优VDITC, 从而可得出图的最优VDVITC. Chen等[10]提出了图的VDITC和图的VDVITC, 从而确定了完全图、 完全二部图、 轮、 扇、 正规双星、 路、 圈等图类的点可区别的Ⅰ-全色数以及点可区别的Ⅵ-全色数, 并提出了以下猜想.

苗婷婷等[11-12]研究了两条路的联图、 圈与路的联图、 圈与圈、 圈与轮、 圈与扇的联图的VDITC和VDVITC； 杨晗等[13]研究了m个阶为4的圈的不交并的点可区别的Ⅰ-全染色和Ⅵ-全染色. 本文通过构造m个长为15的圈……