广义-Mycielski图的集合点色数

贾泽乐, 李沐春

(兰州交通大学 应用数学研究所， 甘肃 兰州 730070)

0 引 言

图染色是图论中的重要方向之一,在组合分析和实际生活中有着广泛的应用.1952 年,Dirac[1]和Youngs[2]通过四色问题的研究提出了图G的点染色概念,并把所用颜色的最小数称为点色数,记作(G).1973年,Bondy等[3]证明了不包含奇圈和完全图的简单连通图G，满足(G)≤Δ.近年来,图的染色问题已由经典染色问题发展为种类繁多的新型染色问题(如点可区别边染色、Smarandachely邻点全染色和邻点可区别全染色等[4-6]).

2004年,张忠辅等[7]提出了邻点可区别全染色的概念,即在图G满足全染色的前提下,任意两个邻点的色集合不相同.并把所染颜色的最小数称为邻点可区别全色数，记作at(G)，且满足猜想at(G)≤Δ+3.2005年,李敬文等[8]对特殊图的Mycielski图的边染色进行深入研究. 2008年,李沐春等[9]对轮和路的广义-Mycielski图的星全染色做了针对性的研究,并得到它们的星全色数.学者们对于广义-Mycielski图的研究已经成为一个焦点. 2016年,张伟东[10]专门针对广义-Mycielski图的染色问题进行讨论. 2018年,张婷等[11]利用函数构造法,研究并确定了广义-Mycielski图的邻点可区别I-均匀全色数.

设G(V,E)是由顶点集V(G)和边集E(G)组成的简单连通图.其中，Δ和δ表示G中顶点的最大度和最小度,d(u)表示点u的度数,[1,n]表示从1到n这n个数组成的集合. Mycielski′s图是众多图类中重要的一类,以下给出Mycielski′s图的定义.

定义1[12]设G为简单连通图,如果满足:

(1)V(M(G))=V(G)∪V′∪{v}；

(2)E(M(G))=E(G)∪{uw′|u∈V(G),w′∈V′,uw∈E(G)}∪{w′v|w′∈V′}，其中，V′={w′|w∈V}且{v}∩{V(G)∪V′}=∅;

则称M(G)为G的Mycielski′s图.

在Mycielski′s图的基础上,文献[12]从圈的Mycielski′s图出发进行探究,首次引入了第一类广义-Mycielski′s图,具体定义如下:

定义2 设G(V,E)是……