某些頂點對被非多重色集合所區(qū)別的未必正常染色的綜述

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

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

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

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

V-條件: 任意兩個相鄰的頂點被分配以不同的顏色;

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

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

圖G的一個滿足V-條件[分別的,I-條件,E-條件]的一般全染色稱為圖G的IE-全染色[分別的,VE-全染色,VI-全染色]; 圖G的一個同時滿足V-條件及I-條件[分別的,V-條件及E-條件,I-條件及E-條件]的一般全染色稱為圖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)稱為未必正常的全染色. 如果沒有特別說明, 在提及使用了k種顏色時, 通常認(rèn)為所使用的顏色為1, 2, …,k. 對圖G的任意一個未必正常的全染色f及任一z∈V(G)∪E(G), 將z在f下的顏色記為f(z). 圖G的一個k-一般全染色f也經(jīng)常被定義為一個映射f:V(G)∪E(G)→{1, 2, …,k}. 圖G的一個使用了k種顏色的其他 6 種未必正常全染色也經(jīng)常以滿足相應(yīng)的各種不同條件的映射f:V(G)∪E(G)→{1, 2, …,k}的形式來定義.

一個圖的正常全染色(即同時滿足V-條件,I-條件,E-條件的一般全染色)及7種未必正常全染色之間的關(guān)系見圖 1, 對每條箭線來說, 箭尾處的染色一定是箭頭處的染色, 反之未必.

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

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

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

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

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

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

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

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

?對于階為n的圈Cn, 有

?對于階為n的Hamilton圖G, 有

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

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

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

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

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

否則, 當(dāng)G沒有孤立點時, 令

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖2 7種點可區(qū)別的未必正常的全色數(shù)及點可區(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

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

顯然有ζ(G)≤

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

VDITC猜想或ζ(G)+1.

VDVITC猜想或ζ(G)+1.

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

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

VDETC第一猜想對一個沒有孤立頂點且色數(shù)至多為5的圖G, 我們有或η(G)+1.

VDETC第二猜想對一個沒有孤立頂點的圖G, 我們有(G)}.

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

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

VDVETC猜想對一個沒有孤立頂點的圖G, 我們有或η(G)+1.

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

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

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

VDIETC第二猜想對一個簡單圖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”時的證明.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

?若G是非空二部圖, 則

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

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

?設(shè)n≥3, 則

?對樹T, 有

?對任意非空圖G, 有3≤(G)+1; 對任意非空二部圖G, 有

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

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

?對樹T, 有

?對至少 2 階完全圖Kn, 有

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

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

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

?若n≥3, 則

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

AVDVITC猜想對任意圖G, 有

AVDVTC猜想對任意圖G, 有

AVDITC猜想對任意圖G, 有

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

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

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

Huang等[54]將鄰點可區(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).

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

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

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

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

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

8 展 望

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

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

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

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