圖的無圈染色

魏立鵬,何文杰,黃大江,吳文文

(河北工業(yè)大學(xué)理學(xué)院應(yīng)用數(shù)學(xué)研究所,天津 300130)

圖的無圈染色

魏立鵬,何文杰,黃大江,吳文文

(河北工業(yè)大學(xué)理學(xué)院應(yīng)用數(shù)學(xué)研究所,天津 300130)

我們證明最大度Δ≥5的圖的無圈色數(shù)至多是,這個結(jié)果比目前公認(rèn)的最小上界要小。同時得出兩個新的結(jié)論:對任意Δ=5的圖G,有a(G)≤8;對任意Δ=6的圖 G,有a(G)≤12。

無圈染色;無圈色數(shù);最大度

1 引言

設(shè)G=(V(G),E(G))是一個連通的簡單圖, V(G)和E(G)分別表示G的頂點集和邊集。記Δ(G),δ(G)分別是圖G的最大頂點度和最小頂點度。對于任何一點u∈V(G),用N(u)表示u的鄰居的集合。圖G的一個正常k-點染色是用k種顏色對圖G的點集進行染色使得任意相鄰的點染不同的顏色。圖G中的一個圈叫2-色圈如果它在正常著色中只用了二種顏色。一個圖G的無圈染色滿足以下兩點:(i)G是一個正常染色;(ii)G不包含2-色圈(亦即染任意兩種顏色的點的導(dǎo)出子圖是一個森林)。記圖G的無圈色數(shù)a(G)表示圖G無圈染色所需的最少顏色數(shù)。無圈染色的概念最早由 Gr¨unbaum提出,并且進一步進行了研究,見文獻[3-6,8-11]。關(guān)于圖G有固定值的最大度問題,A lon等人利用概率的方法證明:當(dāng)Δ→∞,任何最大度為Δ的圖的無圈染色使用至多O(Δ43)種顏色;同時也存在最大度為Δ的圖的無圈染色需要種顏色。進一步,他們使用婪算法證明了任何一個最大度為Δ的圖使用Δ2+1種顏色。這個結(jié)果后來被改進為a(G)≤Δ(Δ-1)+2。1979,Burnstein證明了對于任何Δ(G)=4的圖a(G)≤5。近年來,Skulrattanakulchai證明了對于任何Δ(G)=3的圖a(G)≤4。對于任何一個最大度為Δ的圖,Fertin和Raspaud改進了A lon等人的結(jié)果,并證明了它的無圈色數(shù)至多是a(G)本文進一步改進了 Fertin和 Raspaud關(guān)于最大度的圖的無圈染色結(jié)果,證明了任何最大度為Δ≥5的圖a(G)在下面的討論中,如果沒有特殊證明,我們都假定Δ≥5。

定理1.1 對于任意Δ≥5的圖G,有a(G)

為了證明這個定理,首先,先證明下面的引理。

引理1.1 對于任意δ(G)<Δ(G)(Δ≥5)的圖G,有a(G)

2 Proof of Lemma 1.1

在證明定理之前,我們先介紹一些定義如下。

定義1 圖G的一個部分染色是V(G)的子集顏色的分配滿足染任意兩種顏色的點集誘導(dǎo)出的子圖是無圈的。

定義2 對于圖G的一個部分染色c,c(u)記作u所染的顏色。Nc(u)是N(u)中所有染色點的集合,SC(nc(u))={c(ui)|ui∈Nc(u)}是N c(u)中所使用的顏色的集合,nc(u)=|Nc(u)|。顯然|SC(nc(u))|≤nc(u)。

定義3 對于圖G的一個部分染色c,對于ux∈Nc(u),并且ux≠u0。如果對應(yīng)于圖G的一個部分染色c,不存在c(u0)=c(ux),那么u0∈Nc(u)叫做u的一個單染色鄰居,u稱為單染色點;否則是u的一個復(fù)染色鄰居,u稱為復(fù)染色點。

定義4 對于圖G的一個部分染色c,設(shè)Nc′(u)表示u所有復(fù)染色鄰居的集合,有nc′(u)=|Nc′(u)|。顯然,nc′(u)≤nc(u)。

為了使讀者有一個更直觀的了解;我們考慮一個最大度Δ≥5的部分染色圖G,u是圖G中一個末染色的點,ui(i=0,1,2,3,4)代表u所染色的鄰居,ci(i=0,1,2)代表u的鄰居所染的顏色。相關(guān)無圈染色定義的解釋在圖1中給出了說明:u是一個復(fù)染色點,u0和u1是u的單染色鄰居,u2、u3和u4稱為u的復(fù)染色鄰居。Nc(u)={u0,u1, u2,u3,u4},nc(u)=5,SC(nc(u))={c0,c1,c2}, N′c(u)={v2,v3,v4},n′c(u)=3。顯然,n′c(u)≤nc(u),|SC(nc(u))|≤nc(u)。

圖1 一個復(fù)染色點u

應(yīng)用貪婪算法證明引理1.1,首先把圖G中的點接線性序排列:使得v1,v2,…,vn滿足:

運滿滿平臺上的520萬卡車司機，按年齡分為60后、70后、80后、90后四個群體。從年齡分布來看，卡車司機中既有快到法定退休年齡的“老司機”，也有剛剛步入社會的“小鮮肉”。

接下來,按上面的頂點序逐一貪婪的染圖G中的點,依次為點vi分配一個最小顏色標(biāo)記,要求分配給vi一種還沒有被它鄰居使用的顏色,并且在每一步染色過程中,需要保證圖G是無圈部分染色。于是,得到下面三個有用的觀察。

觀察2.2 讓Gi是一個無圈染色圖,u=vi+1是圖G中一個未染色的點。為了給u正常染色,它應(yīng)該避免的顏色數(shù)目至多是|SC(nc(u))|≤

很容易檢驗上面兩個觀察是正確的。

觀察2.3 讓Gi是一個無圈染色圖,u=vi+1是圖G中一個未染色的點。如果Nc′(u)={u1, u2,…,unc′(u)},給u染色為了避免出現(xiàn)2-色圈,它應(yīng)該避免的顏色數(shù)目至多是

證明 對于每一個ui(1≤i≤nc′(u)),它的鄰居的顏色數(shù)目是|SC(nc(ui))|。在染u的時候,它需要避免出現(xiàn) 2-色圈的顏色數(shù)目至多是

根據(jù)上面這些觀察,下面給出引理1.1的證明。

證明 設(shè)G是一個無圈染色圖。在圖G中至多使用種顏色,它是足夠染圖G中的點u=vi+1,使得圖Gi+1保持無圈染色。

情況1nc′(u)=0.在這種情況下,u是一個單染色點,給u染色的時候不會出現(xiàn)2-色圈,因此它只需要避免在Nc(u)中出現(xiàn)的至多Δ-1種顏色,而

情況2 2≤nc′(u)≤Δ-2。

(B2)在Nc(u)中有一種顏色只出現(xiàn)二次。不失一般性,可以假定在Nc(u)中u1和u2有相同的顏色。首先重染其中的一個,比如u1,根據(jù)上面的點序,我們認(rèn)為u1在u2的后面。為了完成這個任務(wù),考慮u1的兩個染色的鄰居有相同的顏色,比如u11和u12。

(a)在Gi{u1}中,如果|SC(nc(u11))|=|SC (nc(u12))|≤Δ-2,可以重新染u1,使得u1和u2使用彼此不同的顏色。在重染u1時,它可以使用的 顏 色 數(shù) 目 至 少 是」種顏色為了回避可能出現(xiàn)的2-色圈,Δ-2種顏色為了保持正常染色,最后一種顏色是u1的最初顏色。在這個在重染過程之后,我們得到了圖Gi的一個新無圈染色,并且滿足nc′(u)≤Δ-2(根據(jù)G的新部分染色,u2一定變成了u的一個單染色鄰居)。因此,根據(jù)上面的情況2,為了無圈的染u,它需要至多種顏色。

(b)在Gi{u1}中,如果u11和u12至少有一個(比如u11)滿足|SC(nc(u11))|=Δ-1,我們重染u11。在重染u11時,它需要避兔至多(Δ-1)+(Δ種顏色,而后得到Giu1的一個新染色,使得|SC(nc(u1))|=Δ-1。接下來重新染u1使得u1和u2有彼此不相同的顏色(根據(jù)情況2.2)。這些重染操作之后,余下的工作按照上面的情況2處理。綜合上面的討論,我們完成了引理1.1的證明。

3 Proof of Theorem 1.1

在下文中,我們假定圖G是Δ-正則的。設(shè)圖G＊是由圖G刪除一個點x(非割點)得到的。圖G＊是有n-1個點的圖,并且有δ(G＊)<Δ, NG(x)={x1,x2,…,xΔ}。不失一般性,NG＊(xΔ)∩{V(G＊)NG(x)}≠φ(根據(jù)G＊的連通性)。我們把圖G＊中的點按一個線性序排列:使得v1, v2,…,vn-1滿足:

在這種情況下,圖G＊染色和上面證明圖G的δ<Δ染色部分一樣。首先用彼此不同的顏色ci(i=1,2,…,Δ-1)染vi。只需要貪婪的染vi(i=Δ,Δ+1,…,n-1)用至多種顏色。最后,對于G＊=G{x},我們得到一個無圈染色φ,它需要至多種顏色。注意vi(i=1,2,…Δ-1)的顏色ci在整個染色過程中是不變的。為了證明這一點,我們給出下面的引理。

引理3.1 在上面染色過程中,能夠保證vi(i=1,2,…Δ-1)的顏色ci是不變的。

證明 在上面染色過程中,當(dāng)我們需要重新給某一點y染色時,有兩種情況。第一種情況,在引理1.1的證明中,情況2的子情況2.2,情況3中的子情況 3.1和 3.2(B2)(b)使得|SC(nc (y))|=Δ-1。但是vi(i=1,2,…,Δ-1)必須鄰接vn,而且在整個圖G染色之前,vn沒有被染色,因此在G的任何一個部分染色中,有|SC(nc (vi))|≤Δ-2(i=1,2,…,Δ-1)。第二種情況,在引理1.1的證明中,情況 3中的子情況 3.2(B2)(b)中存在兩個點(比如u1和u2)具有相同的顏色。但是vi(i=1,2,…,Δ-1)的顏色ci是彼此不同的。因此,u1和u2至少有一個不在vi(i=1,2,…,Δ-1)中,它位于vi(i=1,2,…,Δ-1)的后面。所以我們不選擇任何一個vi(i=1,2,…,Δ-1)重染。

下面的兩個推論,由定理1.1令Δ(G)=5,6得到,并且改進了文獻[8-9]的結(jié)果。

推論3.1 對于任意Δ=5的圖G,有a(G)≤8。

推論3.2 對于任意Δ=6的圖G,有a(G)≤12。

[1] M.O.Albertson,G.G.Chappell,H.A.Kierstead,A. Kündgen,and R.Ramamurthi,Coloring w ith no 2-coloredp4′s.The Electronic Journal of Combinatorics,2004,11 (1).

[2] N.Alon,C.McDiarmid,and B.Reed.Acyclic colorings of graphs.Random Structures and A lgorithm s,1991,2:277 -288.

[3] O.V.Borodin,On acyclic coloring of planar graphs,Discrete Math.25(1979).211-236.

[4] O.V.Borodin,A.V.Kostochka,A.Raspanud and E.Sopena,Acyclic coloring of 1-planar graphs,Discrete Applied Mathematics,114(2001),29-41.

[5] O.V.Borodin,A.V.Kostochka,and D.R.Woodwall,Acyclic coloring of p lanar graphs w ith large girth,J.London Math.Soc.,60(1999),344-352.

[6] M.I.Burnstein,Every 4-valent graph has an acyic 5-coloring(in russian),Sooˇb scˇ.J.Akad.Nauk Grucin.SSR 93 (1979),21-24.

[7] B.Grünbaum,Acyclic colorings of planar graphs,Iarael J. M ath.14(1973),390-408.

[8] Guillaume Fertin,and AndréRaspaud,Acyclic coloring of Graphs of Maximum degreeΔ,in European Conference on Combinatorics Graph Theory,and App lications,pp. (2005),389-396.

[9] Guillaume Fertin and AndréRaspaud,Acyclic coloring of Graphs of Maximum degree five:nine colors are enough, Inform.Process.Lett.105(2008),65-72.

[10] G.Fertin,E.Godard and A.Raspaud,Acyclic and k-distance coloring of the grid,Information Processing Letters. 87(2003),51-58.

[11] S.Skulrattanakulchai,Acyclic colo ring of subcubic graphs, Information Processing Letters.92(2004),161-167.

Acyclic coloring of graphs

WEILi-peng,HEWen-jie,HUANGDa-jiang,WUWen-wen

(A pplied M athematics Institute,Hebei University of Technology,Tianjin300401,China)

Any graph w ith maximum degreeΔ≥5 has acyclic chromatic number at mosta(G)≤」is p roved.This result is less than the best general upper bounda(G)and two new conclvsions are drew as follow s:a(G)≤8,if any graph ofΔ=5;a(G)≤12,if any graph ofΔ=6.

Acyclic colo ring;Acyclic chromatic num ber;M aximmm um degree

O157

:A

1001-9383(2010)04-0004-05

2010-09-21

國家自然科學(xué)基金資助項目(10871058)

魏立鵬(1984-),男,內(nèi)蒙赤峰人,研究生,研究方向:圖的染色問題.