賈澤樂(lè), 李沐春

(蘭州交通大學(xué) 應(yīng)用數(shù)學(xué)研究所， 甘肅 蘭州 730070)

0 引 言

圖染色是圖論中的重要方向之一,在組合分析和實(shí)際生活中有著廣泛的應(yīng)用.1952 年,Dirac[1]和Youngs[2]通過(guò)四色問(wèn)題的研究提出了圖G的點(diǎn)染色概念,并把所用顏色的最小數(shù)稱為點(diǎn)色數(shù),記作(G).1973年,Bondy等[3]證明了不包含奇圈和完全圖的簡(jiǎn)單連通圖G，滿足(G)≤Δ.近年來(lái),圖的染色問(wèn)題已由經(jīng)典染色問(wèn)題發(fā)展為種類繁多的新型染色問(wèn)題(如點(diǎn)可區(qū)別邊染色、Smarandachely鄰點(diǎn)全染色和鄰點(diǎn)可區(qū)別全染色等[4-6]).

2004年,張忠輔等[7]提出了鄰點(diǎn)可區(qū)別全染色的概念,即在圖G滿足全染色的前提下,任意兩個(gè)鄰點(diǎn)的色集合不相同.并把所染顏色的最小數(shù)稱為鄰點(diǎn)可區(qū)別全色數(shù)，記作at(G)，且滿足猜想at(G)≤Δ+3.2005年,李敬文等[8]對(duì)特殊圖的Mycielski圖的邊染色進(jìn)行深入研究. 2008年,李沐春等[9]對(duì)輪和路的廣義-Mycielski圖的星全染色做了針對(duì)性的研究,并得到它們的星全色數(shù).學(xué)者們對(duì)于廣義-Mycielski圖的研究已經(jīng)成為一個(gè)焦點(diǎn). 2016年,張偉東[10]專門針對(duì)廣義-Mycielski圖的染色問(wèn)題進(jìn)行討論. 2018年,張婷等[11]利用函數(shù)構(gòu)造法,研究并確定了廣義-Mycielski圖的鄰點(diǎn)可區(qū)別I-均勻全色數(shù).

設(shè)G(V,E)是由頂點(diǎn)集V(G)和邊集E(G)組成的簡(jiǎn)單連通圖.其中，Δ和δ表示G中頂點(diǎn)的最大度和最小度,d(u)表示點(diǎn)u的度數(shù),[1,n]表示從1到n這n個(gè)數(shù)組成的集合. Mycielski′s圖是眾多圖類中重要的一類,以下給出Mycielski′s圖的定義.

定義1[12]設(shè)G為簡(jiǎn)單連通圖,如果滿足:

(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圖的基礎(chǔ)上,文獻(xiàn)[12]從圈的Mycielski′s圖出發(fā)進(jìn)行探究,首次引入了第一類廣義-Mycielski′s圖,具體定義如下:

定義2 設(shè)G(V,E)是擁有n個(gè)頂點(diǎn)的簡(jiǎn)單連通圖,m為自然數(shù),如果滿足:

則稱Nm(G)為G的第一類廣義-Mycielski′s圖 (圖1，Nm(Pn)所示).

圖1 第一、第二類廣義-Mycielski′s圖Fig.1 The first general-Mycielski′s graph Nm(Pn) and second general-Mycielski′s graph Mm(Pn)

隨后,張東翰[13]針對(duì)路的廣義-Mycielski′s圖分兩種情況進(jìn)行討論,并定義了第二類廣義-Mycielski′s圖.

定義3[13]設(shè)G(V,E)是擁有n個(gè)頂點(diǎn)的簡(jiǎn)單連通圖,m為自然數(shù),如果滿足:

則稱Mm(G)為G的第二類廣義-Mycielski′s圖(圖1,Mm(Pn)所示).

對(duì)染色函數(shù)而言,一個(gè)自然的想法是能否將其從單元素的染色推廣到集合下的著色,然后確定圖的最小色數(shù),目前不得而知.本文結(jié)合圖的點(diǎn)染色和鄰點(diǎn)可區(qū)別全染色，首先引入圖的集合點(diǎn)染色概念,具體如下:

定義4 對(duì)于簡(jiǎn)單連通圖G,令f是V(G)到集合X中非空子集的一個(gè)映射,其中，X={1,2,…,k},k為正整數(shù),如果滿足：

(1)?u∈V(G),有|f(u)|≥d(u);

(2)對(duì)?uv∈E(G),有f(u)≠f(v)且f(u)∩f(v)≠?.

則稱f為圖G的集合點(diǎn)染色,簡(jiǎn)記作圖G的k-SVC,并稱s(G)=min{k|G具有k-SVC}為G的集合點(diǎn)色數(shù).

在圖染色研究中,構(gòu)造染色函數(shù)法是確定色數(shù)最重要的工具之一.第一、第二廣義-Mycielski′s圖作為重要的兩類圖,廣泛受到學(xué)者們的關(guān)注.本文應(yīng)用構(gòu)造染色函數(shù)法給出了第一、第二廣義-Mycielski′s圖的集合點(diǎn)染色及其對(duì)應(yīng)的點(diǎn)色數(shù).

1 主要結(jié)論

定理1設(shè)G是擁有n(n≥2)個(gè)頂點(diǎn)且最大度為Δ(Δ≥2)的簡(jiǎn)單連通圖,同時(shí)s(G)=k, 則s(M(G))=max{k+Δ,n}.

情形1當(dāng)γ>|V(G)|時(shí),分兩種情況進(jìn)行討論.

情形1.1若頂點(diǎn)集Vi中的最大度點(diǎn)相鄰.

由Mycielski-圖定義知,在G中的最大度頂點(diǎn)同時(shí)也是M(G)的最大度頂點(diǎn). 故有：

2(k-1)=2k-2，

即集合點(diǎn)色數(shù)為2k-1.因此,M(G)有一個(gè)(k+Δ)-SVC染色.

下面構(gòu)造M(G)的染色函數(shù)f*如下：

當(dāng)1≤j≤n時(shí)，

情形1.2若頂點(diǎn)集Vi中的最大度點(diǎn)不相鄰.

由Mycielski-圖定義知,在G中是最大度頂點(diǎn)同時(shí)在M(G)也是最大度頂點(diǎn). 從而有

即集合點(diǎn)色數(shù)為2k.因此，M(G)有一個(gè)(k+Δ)-SVC染色.

構(gòu)造M(G)的染色函數(shù)f*如下：

當(dāng)1≤j≤n時(shí)，

情形2當(dāng)γ=|V(G)|時(shí),分兩種情況進(jìn)行討論.

情形2.1若頂點(diǎn)集Vi中的最大度點(diǎn)相鄰.

由Mycielski-圖定義知,在G中的最大度頂點(diǎn)同時(shí)也是M(G)的最大度頂點(diǎn). 同時(shí)有

即集合點(diǎn)色數(shù)為2k-1.因此,M(G)有一個(gè)(k+Δ)-SVC染色.

構(gòu)造M(G)的染色函數(shù)f*如下：

當(dāng)1≤j≤n時(shí)，

情形2.2若頂點(diǎn)集Vi中的最大度點(diǎn)不相鄰.

由Mycielski-圖定義知,在G中是最大度頂點(diǎn)同時(shí)在M(G)也是最大度頂點(diǎn). 從而有

即集合點(diǎn)色數(shù)為2k.因此,M(G)有一個(gè)(k+Δ)-SVC染色.

構(gòu)造M(G)的染色函數(shù)f*如下：

當(dāng)1≤j≤n時(shí)，

情形3當(dāng)γ<|V(G)|時(shí),分兩種情況進(jìn)行討論.

情形3.1若頂點(diǎn)集Vi中的最大度點(diǎn)相鄰.

由Mycielski-圖定義知,在G中的最大度頂點(diǎn)同時(shí)也是M(G)的最大度頂點(diǎn). 同時(shí)有

又因?yàn)棣?|V(G)|=n,即集合點(diǎn)色數(shù)為n.因此,M(G)有一個(gè)n-SVC染色.

構(gòu)造M(G)的染色函數(shù)f*如下：

當(dāng)1≤j≤n時(shí)，

情形3.2若頂點(diǎn)集Vi中的最大度點(diǎn)不相鄰.

由Mycielski-圖定義知,在G中是最大度頂點(diǎn)同時(shí)在M(G)也是最大度頂點(diǎn). 從而有

又因?yàn)棣?|V(G)|=n,即集合點(diǎn)色數(shù)為n.因此,M(G)有一個(gè)n-SVC染色.

構(gòu)造M(G)的染色函數(shù)f*如下：

當(dāng)1≤j≤n時(shí)，

綜上所述,結(jié)論成立.

定理2設(shè)G是擁有n(n≥2)個(gè)頂點(diǎn)且最大度為Δ(Δ≥2)的簡(jiǎn)單連通圖,同時(shí)s(G)=k, 則G的第一類廣義-Mycielski圖的集合點(diǎn)色數(shù)為s(Nm(G))=k+Δ.

情形4若頂點(diǎn)集Vi中的最大度點(diǎn)相鄰.

由第一類廣義-Mycielski圖定義知,在G中的最大度頂點(diǎn)同時(shí)也是Nm(G)的最大度頂點(diǎn).同時(shí)有

即集合點(diǎn)色數(shù)為2k-1,因此,Nm(G)有一個(gè)(k+Δ)-SVC染色.

構(gòu)造Nm(G)的染色函數(shù)f*如下：

當(dāng)1≤i≤m-1,1≤j≤n時(shí)，

情形5若頂點(diǎn)集Vi中的最大度點(diǎn)不相鄰.

由第一類廣義-Mycielski圖定義知,在G中的最大度頂點(diǎn)同時(shí)也是Nm(G)的最大度頂點(diǎn).從而有

即集合點(diǎn)色數(shù)為2k,因此Nm(G)有一個(gè)(k+Δ)-SVC染色.

構(gòu)造Nm(G)的染色函數(shù)f*如下：

當(dāng)1≤i≤m-1,1≤j≤n時(shí)，

綜上所述,結(jié)論成立.

定理3設(shè)G是擁有n(n≥2)個(gè)頂點(diǎn)且最大度為Δ(Δ≥2)的簡(jiǎn)單連通圖,同時(shí)s(G)=k, 則G的第二類廣義-Mycielski圖的集合點(diǎn)色數(shù)為s(Mm(G))=max{k+Δ,n}.

情形6當(dāng)α>d(v)時(shí),分兩種情況進(jìn)行討論.

情形6.1若頂點(diǎn)集Vi中的最大度頂點(diǎn)相鄰.

由第二類廣義-Mycielski圖定義知,在原圖G中是最大度頂點(diǎn)，同時(shí)也是Mm(G)的最大度頂點(diǎn).有

即集合點(diǎn)色數(shù)為2k-1.因此,Mm(G)有一個(gè)(k+Δ)-SVC染色.

構(gòu)造Mm(G)的染色函數(shù)f*如下：

當(dāng)1≤j≤n時(shí)，

情形6.2若頂點(diǎn)集Vi中的最大度頂點(diǎn)不相鄰.

由第二類廣義-Mycielski圖定義知,在G中的最大度頂點(diǎn)同時(shí)也是Mm(G)的最大度頂點(diǎn).從而有

2Δ=2k=k+Δ.

即集合點(diǎn)色數(shù)為2k,因此,Mm(G)有一個(gè)(k+Δ)-SVC染色.

構(gòu)造Mm(G)的染色函數(shù)f*如下：

當(dāng)1≤j≤n時(shí)，

情形7 當(dāng)α=d(v)時(shí),分兩種情況進(jìn)行討論.

情形7.1若頂點(diǎn)集Vi中的最大度點(diǎn)相鄰.

由第二類廣義-Mycielski 圖定義知,在G中的最大度頂點(diǎn)，同時(shí)也是Mm(G)的最大度頂點(diǎn).有

即集合點(diǎn)色數(shù)為2k-1.因此,Mm(G)有一個(gè)(k+Δ)-SVC染色.

構(gòu)造Mm(G)的染色函數(shù)f*如下：

當(dāng)1≤j≤n時(shí)，

情形7.2若頂點(diǎn)集Vi中的最大度點(diǎn)不相鄰.

由第二類廣義-Mycielski圖定義知,在G中是最大度頂點(diǎn)同時(shí)在Mm(G)也是最大度頂點(diǎn).有

即集合點(diǎn)色數(shù)為2k.因此，Mm(G)有一個(gè)(k+Δ)-SVC染色.

構(gòu)造Mm(G)的染色函數(shù)f*如下：

當(dāng)1≤j≤n時(shí),

情形8當(dāng)α

情形8.1若頂點(diǎn)集Vi中的最大度點(diǎn)相鄰.

由第二類廣義-Mycielski圖定義與α

構(gòu)造Mm(G)的染色函數(shù)f*如下：

當(dāng)1≤j≤n時(shí),

情形8.2若頂點(diǎn)集Vi中的最大度點(diǎn)不相鄰.

由第二類廣義-Mycielski圖定義與α

構(gòu)造Mm(G)的染色函數(shù)f*如下：

當(dāng)1≤j≤n時(shí)，

綜上所述,結(jié)論成立.