图mC8的点可区别Ⅰ-全染色和Ⅵ-全染色

杨 晗,陈祥恩

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

1 引言与预备知识

本文所考虑的图均为有限无向简单图. 目前,关于图的点可区别正常边染色与图的点可区别一般边染色研究已有很多结果[1-9].

设f:V∪E→{1,2,…,k}为图G的一个全染色(正常或未必正常). 对图G的每个顶点x,用Cf(x)表示在f下点x的颜色及全体与x关联的边的颜色构成的集合(非多重集),称其为x的色集合或调色板. 设f为图G的一个正常全染色. 若对∀u,v∈V,u≠v,总有C(u)≠C(v),则称f为G的点可区别全染色(VDTC)[10-11]. 本文考虑图的点可区别的一类未必正常的全染色.

用ni(G)表示图G的度为i的顶点个数,δ≤i≤Δ,这里δ和Δ分别表示图G的最小度和最大度. 记

由于图的点可区别Ⅰ-全染色必为图的点可区别Ⅵ-全染色,故本文只讨论图的点可区别Ⅰ-全染色,相应的图的点可区别Ⅵ-全染色由此可得.

文献[12]提出了图的点可区别Ⅰ-全染色及图的点可区别Ⅵ-全染色,并确定了完全图、完全二部图、轮、扇、正规双星、路、圈、两条同阶圈的联图、一类近完全图等图类的点可区别Ⅰ-全色数以及点可区别Ⅵ-全色数,并提出了下列猜想.

文献[14-16]研究了两条路的联图、圈与路的联图、圈与圈、圈与轮、圈与扇的联图的点可区别Ⅰ-全染色和Ⅵ-全染色. 文献[17]研究了m个长为4的圈不交并mC4的点可区别全染色. 本文构造m个长为8的圈不交并mC8的最优点可区别Ⅰ-全染色,并确定mC8的点可区别Ⅰ-全色数,当m≥2时,即为ζ(G). 利用命题1确定当m≥2时,mC8的点可区别Ⅵ-全色数. 结果表明,VDITC 猜想和VDVITC猜想对图mC8成立.

首先,对任意的k≥6,构造(k-1)×(k-1)阶矩阵Ak,使矩阵Ak的元……