(西北師范大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院, 甘肅 蘭州 730070)

1 引言及準(zhǔn)備工作

本文所考慮的圖均為有限無(wú)向簡(jiǎn)單圖. 關(guān)于圖的可區(qū)別的正常邊染色和全染色, 可以參看文獻(xiàn)[1]. 在這篇綜述文章里, 重點(diǎn)介紹了圖的被非多重色集合可區(qū)別的未必正常的邊染色和全染色.

所謂圖G的一個(gè)一般全染色是指若干種顏色對(duì)圖G的全體頂點(diǎn)及所有邊的一個(gè)分配. 注意, 這里并不要求下面的三個(gè)條件成立:

V-條件: 任意兩個(gè)相鄰的頂點(diǎn)被分配以不同的顏色;

I-條件: 任意一條邊與其(每個(gè))端點(diǎn)被分配以不同的顏色;

E-條件: 任意兩條相鄰的邊被分配以不同的顏色.

圖G的一個(gè)滿(mǎn)足V-條件[分別的,I-條件,E-條件]的一般全染色稱(chēng)為圖G的IE-全染色[分別的,VE-全染色,VI-全染色]; 圖G的一個(gè)同時(shí)滿(mǎn)足V-條件及I-條件[分別的,V-條件及E-條件,I-條件及E-條件]的一般全染色稱(chēng)為圖G的E-全染色[分別的,I-全染色,V-全染色]. 使用了k種顏色的一般全染色[分別的,V-,I-,E-,VI-,VE-,IE-全染色]叫做k-一般全染色[分別的,k-V-,k-I-,k-E-,k-VI-,k-VE-,k-IE-全染色]. 這7種染色統(tǒng)稱(chēng)為未必正常的全染色. 如果沒(méi)有特別說(shuō)明, 在提及使用了k種顏色時(shí), 通常認(rèn)為所使用的顏色為1, 2, …,k. 對(duì)圖G的任意一個(gè)未必正常的全染色f及任一z∈V(G)∪E(G), 將z在f下的顏色記為f(z). 圖G的一個(gè)k-一般全染色f也經(jīng)常被定義為一個(gè)映射f:V(G)∪E(G)→{1, 2, …,k}. 圖G的一個(gè)使用了k種顏色的其他 6 種未必正常全染色也經(jīng)常以滿(mǎn)足相應(yīng)的各種不同條件的映射f:V(G)∪E(G)→{1, 2, …,k}的形式來(lái)定義.

一個(gè)圖的正常全染色(即同時(shí)滿(mǎn)足V-條件,I-條件,E-條件的一般全染色)及7種未必正常全染色之間的關(guān)系見(jiàn)圖 1, 對(duì)每條箭線(xiàn)來(lái)說(shuō), 箭尾處的染色一定是箭頭處的染色, 反之未必.

圖1 正常全染色及7種未必正常全染色之間的關(guān)系Fig.1 The relation among proper total coloring and 7 types of not necessarily proper total colorings

在某個(gè)未必正常染色下兩個(gè)頂點(diǎn)被非多重色集合[分別的, 多重色集合, 色和, 色積, 模色和]所區(qū)別是指這兩個(gè)頂點(diǎn)在所給染色下的非多重色集合[分別的, 多重色集合, 色和, 色積, 模色和]不同.

本文涉及的頂點(diǎn)被區(qū)別的方式為被非多重色集合所區(qū)別. 按照區(qū)別的對(duì)象分為：任意兩個(gè)不同頂點(diǎn)被區(qū)別, 任意兩個(gè)相鄰頂點(diǎn)被區(qū)別, 亦或是任意兩個(gè)距離不超過(guò)d的不同頂點(diǎn)被區(qū)別. 我們提到的邊染色及全染色都是未必正常的.

2 點(diǎn)可區(qū)別一般邊染色

設(shè)f是圖G的一個(gè)一般邊染色. 如果對(duì)圖G的任意兩個(gè)不同頂點(diǎn)u和v, 都有S(u)≠S(v), 那么f稱(chēng)為是點(diǎn)可區(qū)別的. 對(duì)圖G進(jìn)行點(diǎn)可區(qū)別一般邊染色所需最少顏色的數(shù)目記為0(G), 稱(chēng)為圖G的點(diǎn)可區(qū)別一般邊色數(shù). 這種染色是由 Harary等[2]于1985年提出的，這是最早的有關(guān)可區(qū)別染色的文獻(xiàn). 因此有理由認(rèn)為 Harary等是可區(qū)別染色的開(kāi)創(chuàng)者. 該文對(duì)“點(diǎn)可區(qū)別”采用了“point distinguishing”的書(shū)寫(xiě)方式. 當(dāng)圖G含有至少兩個(gè)孤立點(diǎn)或含孤立邊時(shí), 規(guī)定0(G)=∞. 該文給出了如下結(jié)論：

? 若H是圖G的生成子圖, 則0(G)≤0(H)+1.

?設(shè)圖G的階為n, 則0(G)≥log2n.

?對(duì)于階為n的路Pn(n≥3), 有

?對(duì)于階為n的圈Cn, 有

?對(duì)于階為n的Hamilton圖G, 有

?對(duì)于階為n(n≥3)的完全圖Kn, 有0(Kn)=「log2n?+1.

?當(dāng)m≤n且m≥「log2n?+1時(shí), 有0(Km, n)≤「log2n?+2.

? 設(shè)n≥2, 則「log2n?+1≤0(Kn, n)≤「log2n?+2.

? 設(shè)Qn為n維超立方,n≥2, 則0(Qn)=n+1.

確定完全二部圖的點(diǎn)可區(qū)別一般邊色數(shù)十分困難. 已經(jīng)取得了許多成果參見(jiàn)文獻(xiàn)[3-7]. 在文獻(xiàn)[8]中, 作者提出了一個(gè)指標(biāo). 設(shè)G是一個(gè)vdec圖(即最多含一個(gè)孤立點(diǎn)且不含孤立邊的圖). 讓ni(G)表示圖G的度為i的頂點(diǎn)數(shù)目,δ≤i≤Δ, 這里δ與 Δ分別表示圖G的最小度與最大度. 當(dāng)G有一個(gè)孤立點(diǎn)時(shí), 令

否則, 當(dāng)G沒(méi)有孤立點(diǎn)時(shí), 令

文獻(xiàn)[8]中給出了p條階至少為 3 的路的不交并能夠用2p+r種顏色(r為非負(fù)整數(shù)) 進(jìn)行點(diǎn)可區(qū)別一般邊染色的充分必要條件, 并給出了結(jié)論: 當(dāng)G為若干條階至少為 3 的不交路時(shí), 有0(G)=ρ(G)或ρ(G)+1. 基于已有結(jié)論和事實(shí)0(3C3)=ρ(3C3)+2, 該文提出了如下猜想.

VDGEC猜想[8]如果G是一個(gè)vdec圖, 則ρ(G)≤0(G)≤ρ(G)+2. 此外

3 鄰點(diǎn)可區(qū)別一般邊染色

設(shè)f是圖G的一個(gè)一般邊染色. 如果對(duì)圖G的任意兩個(gè)相鄰頂點(diǎn)u和v, 都有S(u)≠S(v), 那么f稱(chēng)為是鄰點(diǎn)可區(qū)別的. 對(duì)圖G進(jìn)行鄰點(diǎn)可區(qū)別一般邊染色所需的最少顏色的數(shù)目記為gndi(G)或者稱(chēng)為圖G的鄰點(diǎn)可區(qū)別一般邊色數(shù). 這種染色是由Gy?ri等[9]于2008年提出的.在文獻(xiàn)[9]中得到了“至少含兩條邊的連通二部圖的鄰點(diǎn)可區(qū)別一般邊色數(shù)不超過(guò)3”. 在文獻(xiàn)[10]中給出下述結(jié)論.

定理[10]若G是無(wú)孤立邊的圖, 且其(正常點(diǎn))色數(shù)至少為3, 則(G)?+1.

其他相關(guān)成果可見(jiàn)參考文獻(xiàn)[11-14].

4 D(d)-點(diǎn)可區(qū)別一般邊染色

文獻(xiàn)[15]中引入了圖的D(d)-點(diǎn)可區(qū)別一般邊染色.設(shè)d是正整數(shù), 如果?u,v∈V(G),一旦1≤dG(u,v)≤d, 都有S(u)≠S(v), 那么f稱(chēng)為G的使用了k種色的D(d)-點(diǎn)可區(qū)別一般邊染色, 對(duì)一個(gè)圖G進(jìn)行D(d)-點(diǎn)可區(qū)別一般邊染色所需的最少顏色數(shù)稱(chēng)為圖G的D(d)-點(diǎn)可區(qū)別一般邊色數(shù), 記為

文獻(xiàn)[15]中對(duì)d=2的情形做了討論,得到了路、圈、星、雙星、扇、輪的D(2)-點(diǎn)可區(qū)別一般邊色數(shù), 基于此, 提出了一個(gè)猜想.

對(duì)階不小于 3 的連通圖G, 令mi表示圖G中使得任意兩點(diǎn)間的距離不超過(guò)d的度不超過(guò)i的頂點(diǎn)的最大數(shù)目,i=δ,δ+1, …,Δ, 且記

D(2)-VDGEC猜想[15]如果G是階至少為 3 的連通圖, 那么μ′2(G)≤

設(shè)圖G為連通圖, 其 2 距離色數(shù)2(G)=4, 稱(chēng)G的一個(gè)以X,Y,Z,W為色類(lèi)的 2 距離 4 著色是穩(wěn)定的 (色類(lèi)是指在圖的頂點(diǎn)著色下染同一種顏色的所有頂點(diǎn)組成的集合), 如果對(duì)W中任意 2 度頂點(diǎn)w, 設(shè)u,v為w的鄰點(diǎn), 有

(i)當(dāng)d(u)=1,d(v)=3時(shí),v的 除w之外的兩個(gè)鄰點(diǎn)至少有一個(gè)為1度;

(ii)當(dāng)d(u)>1且d(v)>1時(shí), 若u,v∈X∪Y, 則在X∪Y中任意一個(gè)與w的距離為1或2的點(diǎn)在Z中有鄰點(diǎn);若u,v∈X∪Z, 則在X∪Z中任意一個(gè)與w的距離為1或2的點(diǎn)在Y中有鄰點(diǎn); 若u,v∈Y∪Z, 則在Y∪Z中任意一個(gè)與w的距離為1或2 的點(diǎn)在X中有鄰點(diǎn).

文獻(xiàn)[15]中對(duì)于2距離色數(shù)等于3及4的圖的D(2)-點(diǎn)可區(qū)別一般邊色數(shù)做了探討,得到了具有穩(wěn)定2距離4著色的連通圖的D(2)-點(diǎn)可區(qū)別一般邊染色為3的結(jié)論, 同時(shí)提出了一個(gè)公開(kāi)問(wèn)題.

公開(kāi)問(wèn)題是否對(duì)任意使得2(G)=4的連通圖G都存在穩(wěn)定的2距離4著色?

5 點(diǎn)可區(qū)別的各種未必正常的全染色

設(shè)f為圖G的V-全染色(分別的,E-,I-,VE-,VI-,IE-全染色,一般全染色). 如果對(duì)?u,v∈V,u≠v, 總有C(u)≠C(v), 則稱(chēng)f為點(diǎn)可區(qū)別的. 使用了k種顏色的點(diǎn)可區(qū)別V-全染色簡(jiǎn)記為k-VDVTC. 類(lèi)似的有k-VDETC,k-VDITC,k-VDVETC,k-VDVITC,k-VDIETC,k-VDGTC.

對(duì)一個(gè)圖G進(jìn)行點(diǎn)可區(qū)別V-全染色(分別的, 點(diǎn)可區(qū)別E-,I-,VE-,VI-,IE-, 一般全染色)所需的最少顏色數(shù)目稱(chēng)為圖G的點(diǎn)可區(qū)別V-全色數(shù)(分別的, 點(diǎn)可區(qū)別E-,I-,VE-,VI-,IE-, 一般全色數(shù)), 記為(分別的,,gvt(G)). 比如

圖2 7種點(diǎn)可區(qū)別的未必正常的全色數(shù)及點(diǎn)可區(qū)別正常全色數(shù)之間的關(guān)系

Fig.2 The relation among 7 types of vertex-distinguishing of not necessarily proper total colorings and vertex-distinguishing proper total coloring

對(duì)于圖G, 用ni(G)或ni表示圖G的度為i的頂點(diǎn)個(gè)數(shù),δ≤i≤Δ, 這里δ與Δ分別表示圖G的最小度和最大度.記

顯然有ζ(G)≤

文獻(xiàn)[16]首次提出圖的點(diǎn)可區(qū)別I-全染色及圖的點(diǎn)可區(qū)別VI-全染色, 并且確定了完全圖、完全二部圖、輪、扇、2個(gè)頂點(diǎn)是最大度頂點(diǎn)(它們相鄰)，而其余所有頂點(diǎn)為懸掛點(diǎn)的雙星、路、圈、兩條同階圈的聯(lián)圖、一類(lèi)近完全圖等圖類(lèi)的點(diǎn)可區(qū)別I-全色數(shù)以及點(diǎn)可區(qū)別VI-全色數(shù), 并提出了下面的猜想.

VDITC猜想或ζ(G)+1.

VDVITC猜想或ζ(G)+1.

自然地,VDITC猜想的成立就可推出VDVITC猜想的成立.文獻(xiàn)[17-19]已對(duì)兩條路的聯(lián)圖、圈與路的聯(lián)圖、圈與圈、圈與輪、圈與扇的聯(lián)圖的點(diǎn)可區(qū)別I-全染色和點(diǎn)可區(qū)別VI-全染色進(jìn)行了研究. 張生桂已對(duì)完全圖刪去一個(gè)完美匹配的邊或一個(gè)近完美匹配的邊所得到的圖,nC3mC3,nC4mC4給出其點(diǎn)可區(qū)別I-全色數(shù)和點(diǎn)可區(qū)別VI-全色數(shù). 楊晗已對(duì)mC3,mC4給出其點(diǎn)可區(qū)別I-全色數(shù)和點(diǎn)可區(qū)別VI-全色數(shù). 結(jié)論均支持相關(guān)猜想.

文獻(xiàn)[20]中探討了完全圖、完全二部圖K2, n、 星、輪、扇、路和圈的VDETC, 提出了指標(biāo)η(G)及兩個(gè)猜想. 對(duì)一個(gè)不含孤立頂點(diǎn)的圖G, 令

VDETC第一猜想對(duì)一個(gè)沒(méi)有孤立頂點(diǎn)且色數(shù)至多為5的圖G, 我們有或η(G)+1.

VDETC第二猜想對(duì)一個(gè)沒(méi)有孤立頂點(diǎn)的圖G, 我們有(G)}.

文獻(xiàn)[21]中得出了mC3和mC4的點(diǎn)可區(qū)別E-全色數(shù). 文獻(xiàn)[22-25]中完全討論了完全二部圖K3,n,K4,n,K5,n的VDETC,文獻(xiàn)[26-28]討論了完全二部圖K6,n與K7,n的點(diǎn)可區(qū)別E-全染色. 包麗婭等[29]已分別對(duì)完全二部圖K8,n、K9,n與K10,n的點(diǎn)可區(qū)別E-全染色進(jìn)行了探討.

文獻(xiàn)[30-31]已對(duì)路、圈、完全圖、輪、扇及完全二部圖K1,n,K2,n的點(diǎn)可區(qū)別VE-全染色進(jìn)行了研究, 確定了它們的點(diǎn)可區(qū)別VE-全色數(shù). 據(jù)此分析提出了如下猜想.

VDVETC猜想對(duì)一個(gè)沒(méi)有孤立頂點(diǎn)的圖G, 我們有或η(G)+1.

師志鳳[32]確定了完全二部圖K6,n的點(diǎn)可區(qū)別E-全色數(shù)及點(diǎn)可區(qū)別VE-全色數(shù), 結(jié)論表明VDETC猜想和VDVETC猜想對(duì)于完全二部圖K6,n是成立的.

文獻(xiàn)[33-37]對(duì)圖的點(diǎn)可區(qū)別IE-全染色進(jìn)行了研究. 在文獻(xiàn)[33]中提出了一個(gè)指標(biāo)和三個(gè)猜想. 令

VDIETC第一猜想對(duì)一個(gè)簡(jiǎn)單圖G, 如果它的(正常點(diǎn))色數(shù)(G)≤4, 則或ξ(G)+1.

VDIETC第二猜想對(duì)一個(gè)簡(jiǎn)單圖G, 我們有(G)}.

VDIETC第三猜想設(shè)s使得2s-1≥3m的最小正整數(shù). 當(dāng)2r-2m-1

關(guān)于VDIETC第三猜想, 師瑾[38]給出了“r=m-4,m-3,m-2,s≤m-2”時(shí)的證明.

Liu等[39]提出了一般點(diǎn)可區(qū)別全染色(簡(jiǎn)記為GVDTC), 這一概念就是本文已經(jīng)定義的點(diǎn)可區(qū)別一般全染色(簡(jiǎn)記為VDGTC). 一般點(diǎn)可區(qū)別全色數(shù)實(shí)際上就是本文已經(jīng)定義的點(diǎn)可區(qū)別一般全色數(shù), 記為gvt(G), 這里沿用了文獻(xiàn)[39]中的記號(hào).

文獻(xiàn)[39]中研究了路、圈、星(K1,n)、雙星、三星、輪、扇、完全圖的一般點(diǎn)可區(qū)別全染色, 確定了它們的一般點(diǎn)可區(qū)別全色數(shù). 比如

命題[39]設(shè)Sn是一個(gè)n+1階星,n≥1, 則

基于此, 文獻(xiàn)[40-41]中對(duì)一類(lèi)含有4-圈的單圈圖、2K2K1的冠圖的一般點(diǎn)可區(qū)別全色數(shù)被確定. 李婷[42]還確定一類(lèi)分別含3-圈、4-圈、5-圈的單圈圖, 以及P4、P5、K4的冠圖的一般點(diǎn)可區(qū)別全色數(shù). 在文獻(xiàn)[43]中三星的一般點(diǎn)可區(qū)別全色數(shù)的結(jié)論被給出了詳證.在文獻(xiàn)[44]中探討了K4, n與K5, n的一般點(diǎn)可區(qū)別全色數(shù).

在文獻(xiàn)[45-47]中寇艷芳等對(duì)完全三部圖K1,n,p的點(diǎn)可區(qū)別的IE-全染色及點(diǎn)可區(qū)別的一般全染色進(jìn)行了研究. 筆者指導(dǎo)的研究生張爽、楊佳睿、馬靜靜分別對(duì)完全三部圖K2,n,p,K3,n,p,K4,n,p的點(diǎn)可區(qū)別IE-全染色及點(diǎn)可區(qū)別的一般全染色進(jìn)行了探討.

對(duì)完全二部圖的VDETC,VDVETC,VDIETC,VDGTC的研究具有極大的難度, 因?yàn)檫@四種染色不要求邊染色正常. 這就如同確定完全二部圖的點(diǎn)可區(qū)別一般邊色數(shù)極為困難一樣.

根據(jù)已有的結(jié)論, 我們提出如下猜想.

VDGTC猜想對(duì)一個(gè)簡(jiǎn)單圖G, 有g(shù)vt(G)=ξ(G)或ξ(G)+1.

馬寶林對(duì)路、圈、輪、扇、完全圖、mC3、mC4等圖類(lèi)的點(diǎn)可區(qū)別V-全色數(shù)進(jìn)行了探索, 發(fā)現(xiàn)絕大多數(shù)情況下都與相應(yīng)圖的點(diǎn)可區(qū)別正常全色數(shù)相同. 從而提出如下猜想.

何玉萍[48]發(fā)現(xiàn)了對(duì)于圖mC6,mC7,mC8,mC9來(lái)說(shuō),VDVTC猜想是成立的.

6 鄰點(diǎn)可區(qū)別的各種未必正常的全染色

設(shè)f為圖G的V-全染色(分別的,E-,I-,VE-,VI-,IE-全染色,一般全染色). 若對(duì)?u,v∈V(G), 一旦uv∈E(G),就有C(u)≠C(v), 則稱(chēng)f為鄰點(diǎn)可區(qū)別的. 使用了k種顏色的鄰點(diǎn)可區(qū)別V-全染色簡(jiǎn)記為k-AVDVTC. 類(lèi)似的有k-AVDETC,k-AVDITC,k-AVDVETC,k-AVDVITC,k-AVDIETC,k-AVDGTC.

對(duì)一個(gè)圖G進(jìn)行鄰點(diǎn)可區(qū)別V-全染色(分別的, 鄰點(diǎn)可區(qū)別E-,I-,VE-,VI-,IE-, 一般全染色)所需的最少顏色數(shù)目稱(chēng)為圖G的鄰點(diǎn)可區(qū)別V-全色數(shù)(分別的, 鄰點(diǎn)可區(qū)別E-,I-,VE-,VI-,IE-, 一般全色數(shù)), 記為分別的,,

這7種鄰點(diǎn)可區(qū)別的未必正常的全色數(shù)及鄰點(diǎn)可區(qū)別正常全色數(shù)at(G)之間有類(lèi)比于圖 2 所示的關(guān)系.

在文獻(xiàn)[49]中得到下述結(jié)論：

?若G是非空二部圖, 則

?設(shè)G是一個(gè)色數(shù)為 3 的圖. 則G的鄰點(diǎn)可區(qū)別E-全色數(shù)等于 3 的充分必要條件是存在G的正常 3- 染色h, 使得不存在長(zhǎng)為3的跡u1u2u3u4, 使u1,u2,u3在h下的色不同， 而u1,u4在h下的色相同.

?對(duì)沒(méi)有孤立邊的圖G, 有′(G)≤′a(G), 這里′a(G)表示圖G的鄰點(diǎn)可區(qū)別正常邊色數(shù).

?設(shè)n≥3, 則

?對(duì)樹(shù)T, 有

?對(duì)任意非空?qǐng)DG, 有3≤(G)+1; 對(duì)任意非空二部圖G, 有

?對(duì)任意圖G, 有「log2(G)?+1≤(G)?+2.

?對(duì)任意的色數(shù)至少為 4 的圖G, 有(G)+1)?+1.

?對(duì)樹(shù)T, 有

?對(duì)至少 2 階完全圖Kn, 有

?對(duì)任意圖G, 有max{(G),′(G)}≤≤(G)+′(G).

?設(shè)T是階至少為 2 的樹(shù), 且T有兩個(gè)最大度頂點(diǎn)相鄰, 則

?設(shè)T是階至少為 4 的樹(shù), 且T的最大度頂點(diǎn)唯一或者任意兩個(gè)最大度頂點(diǎn)不相鄰, 則=Δ(T).

?若n≥3, 則

文獻(xiàn)[49]中提出如下三個(gè)猜想.

AVDVITC猜想對(duì)任意圖G, 有

AVDVTC猜想對(duì)任意圖G, 有

AVDITC猜想對(duì)任意圖G, 有

顯然,AVDVTC猜想與AVDITC猜想之一成立就可推出AVDVITC猜想成立.

公開(kāi)問(wèn)題是否存在使得(G)≥4,(G)是2的方冪,且(G)?+1成立的圖.

文獻(xiàn)[50]中確定了路、圈、星和扇的倍圖的鄰點(diǎn)可區(qū)別VI-全色數(shù), 結(jié)論支持AVDVITC猜想. 文獻(xiàn)[51-52]中分別確定了圖的鄰點(diǎn)可區(qū)別VI-全色數(shù)及圖的鄰點(diǎn)可區(qū)別V-全色數(shù)的上界. 文獻(xiàn)[53]中確定了兩類(lèi)冠圖Cm·Cn與Cm·Kn的鄰點(diǎn)可區(qū)別I-全色數(shù), 結(jié)論支持AVDITC猜想.

Huang等[54]將鄰點(diǎn)可區(qū)別一般全色數(shù)記為″gnd(G), 而在文獻(xiàn)[55] 中記為在文獻(xiàn)[54]中給出了下列重要結(jié)論：

?設(shè)G為階至少為 2 的連通圖. 則″gnd(G)=2當(dāng)且僅當(dāng)G是二部圖.

?若H為G的子圖, 則″gnd(H)≤″gnd(G).

?對(duì)沒(méi)有孤立邊且色數(shù)至少為 3 的圖G, 有″gnd(G)=gndi(G).

在文獻(xiàn)[56]中對(duì)一些特殊圖類(lèi)給出了最優(yōu)鄰點(diǎn)可區(qū)別一般全色數(shù)的算法實(shí)現(xiàn).

7 D(d)-點(diǎn)可區(qū)別的各種未必正常的全染色

設(shè)f為圖G的V-全染色(分別的,E-,I-,VE-,VI-,IE-全染色,一般全染色), 而d為正整數(shù). 如果若對(duì)?u,v∈V(G), 一旦1≤dG(u,v)≤d, 就有C(u)≠C(v), 則稱(chēng)f為D(d)-點(diǎn)可區(qū)別的. 使用了k種顏色的D(d)-點(diǎn)可區(qū)別V-全染色簡(jiǎn)記為k-D(d)-VDVTC. 類(lèi)似的有k-D(d)-VDETC,k-D(d)-VDITC,k-D(d)-VDVETC,k-D(d)-VDVITC,k-D(d)-VDIETC,k-D(d)-VDGTC.

對(duì)一個(gè)圖G進(jìn)行D(d)-點(diǎn)可區(qū)別V-全染色(分別的,D(d)-點(diǎn)可區(qū)別E-,I-,VE-,VI-,IE-, 一般全染色)所需最少顏色的數(shù)目稱(chēng)為圖G的D(d)-點(diǎn)可區(qū)別V-全色數(shù)(分別的,D(d)-點(diǎn)可區(qū)別E-,I-,VE-,VI-,IE-, 一般全色數(shù)), 記為(分別的,,

8 展 望

可區(qū)別染色的范圍很廣． 令

那么, 對(duì)任意X∈,Y∈,Z∈, 都可定義“X被Y所區(qū)別的Z染色”, 共有3×5×8=120種. 本文前面僅涉及到Y(jié)=“非多重色集合”的情況.

那么, 對(duì)任意X∈,Y∈1,Z∈1, 可定義“X被Y所區(qū)別的Z染色”. 比如讓X=“任意兩個(gè)相鄰頂點(diǎn)”,Y=“擴(kuò)展色和”,Z=“一般全”, 那么“X被Y所區(qū)別的Z染色”就是文獻(xiàn)[58]中所提出的, 在文獻(xiàn)[59-61]中均有研究.

針對(duì)每一種染色,可能研究的問(wèn)題主要有: 確定一些具體圖類(lèi)的色數(shù); 提出相應(yīng)染色的猜想, 爭(zhēng)取解決猜想, 或研究某類(lèi)圖是否滿(mǎn)足猜想;給出相關(guān)色數(shù)的上界;研究某類(lèi)圖的色數(shù)隨著階增大的變化趨勢(shì);研究(可區(qū)別)染色的某個(gè)特定問(wèn)題,比如尋找子圖的色數(shù)不超過(guò)其母圖相應(yīng)色數(shù)的條件.希望對(duì)可區(qū)別染色理論感興趣的學(xué)者能創(chuàng)新方法、開(kāi)拓思路,做出優(yōu)異成果.