關(guān)于圖的Grundy著色

徐保根

(華東交通大學基礎(chǔ)科學學院,江西南昌330013)

1 定義及引理

本文所指的圖均為無向簡單圖,文中未說明的符號、術(shù)語同于文獻[1]。

設(shè)G=(V,E)為一個圖,若 u∈V(G)則 NG(u)表示 u點在G中的鄰域,d(u)=NG(u)為u點在G中的度。若S?V(G)則G[S]表示S在G中的導出子圖。若u∈V(G)則G-u=G[V{u}]。若M?V(G),則 G-M=G[VM]。G表示G的補圖,Pn、Cn和Kn分別表示n階路、n階圈和n階完全圖。

若G和H為兩個點不交的圖,則用G+H表示圖G與H的直和圖,即在G∪H中將圖G的每個頂點與圖H的所有頂點連接而成的圖。

定義1.1[1]設(shè)G=(V,E)為一個圖,一個函數(shù)被稱為圖G的一個真k-著色函數(shù),如果對任意uv∈E(G)均有f(u)≠f(v)。圖G的(點)色數(shù)定義為χ(G)=min{k 存在圖G的真k-著色函數(shù)}。

近些年來,隨著離散型事物的數(shù)學模型應用性的日益廣泛,圖的著色問題已不再是僅限于對圖的點著色、邊著色及全著色問題,各式各樣的特征著色概念相繼產(chǎn)生,如均勻著色、List著色等,從而使圖的著色理論研究內(nèi)容越來越豐富。Christen C A[2]等人引入了如下Grundy著色概念:

定義1.2[2]對于一個圖G=(V,E),一個函數(shù)f:V→ 1,2,…,k如果滿足條件:

(1)對G中任意相鄰的兩個點u和v,均有f(u)≠f(v);

(2)對任意兩個整數(shù) i和j(1≤i≤j≤k),若f(u)=j,則 NG(u)中必有一點 v,使得 f(v)=i,則稱函數(shù)f為圖G的一個Grundy k-著色函數(shù)。圖G的Grundy色數(shù)定義為 Γ(G)=max{k｜存在圖G的Grundy k-著色函數(shù)}。

由上述定義不難看出:Γ(G)≥χ(G)對任意圖G成立,且對不任意兩個點不交的圖 G和H,均有 Γ(G∪H)=max Γ(G),Γ(H),因此本文中我們只考慮連通圖。

引理1.3[3]對于任意圖 G,若 v∈V(G)則 Γ(G-v)≥Γ(G)-1。

引理1.4 對于任意圖 G,若 Δ=Δ(G)為圖G的最大度,則 Γ(G)≤Δ+1。

證明:由定義1.2知,存在圖G的一個Grundy Γ(G)-著色函數(shù)f及u∈V(G),使得 f(u)=Γ(G),從而對于每個

在NG(u)中必有vi使得f(vi)=i,即有

引理1.4證畢。

引理1.5[3]對于任意圖G,均有

Zaker M[3]研究了二部圖補圖的Grundy色數(shù),并探討了一個圖與其補圖的Grundy色數(shù)的關(guān)系。在本文中我們主要給出圖的Grundy色數(shù)的上界,并確定幾類特殊圖的Grundy色數(shù)。

2 Grundy色數(shù)的上界

我們首先分別給一般圖、樹和二部圖的Grundy色數(shù)的上界。

證明:設(shè) Γ(G)=k,f為圖G的一個真Grundy k-著色函數(shù)。令,顯然 Vi≠φ(i=1,2,…,k)。當1≤i≤j≤k時,記 E且由定義知 aij≥1,從而有

定理2.2 對于任意 n階樹T,均有 Γ(T)≤1+log2n

當1≤Γ(T)≤3時,由于1≤Γ(T)≤2時命題顯然成立。而且3階樹只有 P3,且 Γ(P3)=2,因此,當Γ(T)=3時命題成立。

假若命題對于任何滿足 Γ(T0)≤k-1(k≥4)的樹 T0均成立,即有:若存在 T0的一個真Grundy j-著色函數(shù)(j≤k-1),則

現(xiàn)考慮任意一棵滿足 Γ(T)=k的樹T,f為T的一個真Grundy k-著色函數(shù)。

即命題對于任何滿足 Γ(T)=k的樹T也成立。由歸納原理,定理2.2證畢。

證明:設(shè)G=(V1∪V2,E)為一個二部圖,Γ(G)=k,f為圖G的一個真Grundy k-著色函數(shù)。由定義知:存在u∈V(G)使得 f(u)=k。不妨設(shè) u∈V1,由于,注意到G為二部圖,NG(u)?V2,即有由定義知:存在 v∈V2使得 f(v)=k-1,從而存在 k-2個點 ui∈V1使得f(ui)=i(i=1,2,…,k-2),注意到 u∈ V1且 u≠ui,因此

下面證明此上界是最好可能的。對n為奇數(shù)和偶數(shù)分別構(gòu)造二部圖如下:

當 n=2或3時,顯然有二部圖K1,1和K1,2,且 Γ(K1,1)=Γ(K1,2)=2。下面設(shè) n≥4。

(1)當n=2k(k≥2)為偶數(shù)時,令G=(V1∪V2,E)為一個完全二部圖Kk,k去掉k-1條獨立邊所得的圖。記,所去掉k-1條獨立邊為 uivi(i=1,2,…,k-1)。定義圖G的一個真Grundy k+1-著色函數(shù)f如下:

(2)n=2k+1(k≥2)為奇數(shù)時,在上述定義的圖G中增加一個新頂點w,并將w點鄰接V2中的所有頂點,所得的圖記為G0。定義G0的一個真Grundy k+1-著色函數(shù)f0如下:

f0(w)=k+1,當v≠w時f0(v)=f(v),這里 f的定義同(1)。由此可見

定理2.4 對于任意兩個點不交的圖G和H,均有 Γ(G+H)≥Γ(G)+Γ(H)

證明:設(shè) Γ(G)=k1,Γ(H)=k2,f1和 f2分別為圖 G和圖H 的真Grundy k1和k2-著色函數(shù),定義 G+H的一個Grundy k1+k2-著色函數(shù)f如下:

不難驗證:f為圖G+H的一個Grundy k1+k2-著色函數(shù),因此 Γ(G+H)≥Γ(G)+Γ(H)。定理2.4證畢。

定理2.5 設(shè) n階圖G的度序列為d1≥d2≥d3≥…≥dn,則有

證明:設(shè) Γ(G)=k,用dG(v)表示 v點在G中的度數(shù)。

(反證)假設(shè)存在某個 j(1≤j≤n)使得 Γ(G)=k≥dj+j+1。

證明:設(shè) n階圖G的度序列為d1≥d2≥d3≥…≥dn,由定理2.5知:對每個 i(1≤i≤n),均有 Γ(G)≤di+i,從而有推論2.6證畢。

3 特殊圖的Grundy色數(shù)

下面探討幾類特殊圖的Grundy色數(shù);

定理3.1 設(shè)Pn、Cn和Wn分別表示n階路、圈和輪圖,則有

證明:(1)n=2,3時是顯然的。當 n≥4時,一方面,由引理1.4知 Γ(Pn)≤3。另一方面,可定義Pn的一個真Grundy 3-著色函數(shù)f如下:記(j≥4)。由此可見:當 n≥4時,Γ(Pn)=3。

(2)n=3,4時是顯然的。當 n≥5時,一方面,由引理1.4知 Γ(Cn)≤3。另一方面:當n為奇數(shù)時,可同(1)中一樣地定義Cn的一個真Grundy 3-著色函數(shù)。

當 n為偶數(shù)時,記 Cn=(v1v2v3v4…vn)。定義 f如下:

不難驗證:f為Cn的一個真Grundy 3-著色函數(shù),即當n≥5時,Γ(Cn)=3。

(3)根據(jù)(2)及引理1.5即得,定理3.1證畢。

定理3.2 對任意完全 t-部圖K(m1,m2,…,mt),均有 Γ(K(m1,m2,…,mt))=t

證明:令 G=K(m1,m2,…,mt),V(G)=V1∪V2∪…∪Vt,其中一方面,顯然有 Γ(G)≥χ(G)=t。

另一方面,假若 Γ(G)=k≥t+1,由定義知:存在 G的一個真Grundy k-著色函數(shù)f及一點u∈V(G),使得 f(u)=k,從而在 NG(u)中必有 k-1≥t個頂點ui(1≤i≤k-1),使得 f(ui)=i。而 NG(u)中點至多在t-1部頂點集中,故必有某個Vs包含ui和vj(1≤i≤k-1)。由定義知:NG(uj)中必有某個頂點v使得f(v)=i=f(ui),注意到v?Vs,從而 uiv∈E(G),這與 f的定義矛盾。定理3.2證畢。

[1]BONDY J A,MURTY V S R.Graph Theory with Applications[M].Amsterdam:Elsevier,1976.

[2]CHRISTEN C A,SELKOW S M.Some perfect coloring properties of graphs[J].J.Combin.Theory Ser.B,1979,27(1):49-59.

[3]ZAKER M.Results on the Grundy chromatic number of graphs[J].Discrete Math.,2006,306:3 166-3 173.