沒(méi)有 K5-子式的圖是無(wú)圈5-可染的

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

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

沒(méi)有 K5-子式的圖是無(wú)圈5-可染的

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

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

2006年,Borodin證明了所有平面圖都可以無(wú)圈5-可染。本文推廣Borodin的結(jié)果到?jīng)]有K5-子式的圖。

無(wú)圈k-可染;Wagner圖;沒(méi)有K5-子式的圖;k-和

1 引言

1973年,Grünbaum[5]猜想了每一個(gè)平面圖都有一個(gè)無(wú)圈5-染色同時(shí)證明了每一個(gè)平面圖有一個(gè)無(wú)圈9-染色。1976 A.V.Kostochka[7]證明了每一個(gè)平面圖有一個(gè)無(wú)圈6-染色。1977年, M.O.A lbertson和D.M.Berman[1]證明了每一個(gè)平面圖有一個(gè)無(wú)圈7-染色。最后,O.V.Borodin[3]在2006年證明了 Grünbaum猜想,每一個(gè)平面圖都是無(wú)圈5-可染的。1994年,Thomassen[9]證明了所有平面圖都是 5-可選的。1998年, ?krekovski[8]證明了所有沒(méi)有K5-子式的圖都5-可選。2008年,何等[6]也用另一種方法證明了這個(gè)結(jié)果。本文根據(jù)O.V.Borodin[3]的平面圖無(wú)圈5-可染性,以及無(wú)K5-子式圖的構(gòu)造,證明所有沒(méi)有K5-子式的圖也可以無(wú)圈5-可染。

定理1.1 所有沒(méi)有K5-子式的圖是無(wú)圖5-可染的

在開(kāi)始進(jìn)行證明定理1.1之前,本文需要一些概念和定義。

本文中提到的所有圖都是簡(jiǎn)單,有限且無(wú)向的。長(zhǎng)度為k的圈稱(chēng)為k-圈,由兩種顏色的頂點(diǎn)導(dǎo)出的圈稱(chēng)為雙色圈。圖G的k染色是指k種顏色對(duì)圖G所有點(diǎn)進(jìn)行染色。一個(gè)正常的k染色是指圖G的一個(gè)k染色,并且使得任意相鄰兩個(gè)點(diǎn)染不同顏色。圖G是無(wú)圈k-可染的是指圖G有一個(gè)正常的k染色,同時(shí)使得由兩種染色的點(diǎn)導(dǎo)出的子圖沒(méi)有雙色圈。

圖H稱(chēng)為圖G的一個(gè)子式(minor),如果圖H(或者與H同構(gòu)的圖)可以由圖G通過(guò)一系列的邊收縮,邊刪除或頂點(diǎn)刪除(按任何順序)而獲得。圖G被稱(chēng)為沒(méi)有H-子式圖當(dāng)且僅當(dāng)它沒(méi)有圖H作為一個(gè)子式。一個(gè)圖如果可以畫(huà)在一個(gè)平面上并且使得它的所有邊僅在端點(diǎn)處相交,則認(rèn)為它嵌入在平面或者是平面圖。這樣的一個(gè)畫(huà)法被稱(chēng)為圖的一個(gè)平面嵌入。一個(gè)平面圖是三角化圖當(dāng)且僅當(dāng)它的每一個(gè)面的邊界是一個(gè)3-圈。

Wagner圖(如圖1)是一個(gè)帶有8個(gè)點(diǎn)和12條邊的3-正則圖。它是帶有8個(gè)點(diǎn)的 M?bius ladder圖。作為一個(gè) M?bius ladder,Wagner圖是沒(méi)有K5-子式,但是有K3,3-子式的非平面圖。

假設(shè)圖G1和圖G2是個(gè)k點(diǎn)的完全圖。由G1∪G2刪除G1∩G2的邊得到的圖叫做G1和G2的k-和(見(jiàn)文獻(xiàn)[2]275頁(yè))。

2 構(gòu)造沒(méi)有K5-子式的圖

引理2.1(Wagner定理[10,4])令圖G是一個(gè)沒(méi)有K5-子式的邊極大化圖。假如|G|≥4,則圖G可以從平面三角畫(huà)圖和Wagner圖通過(guò)K3和K2的傳遞被連續(xù)構(gòu)造。

引理2.2 任何一個(gè)沒(méi)有K5-子式的2-連通的圖可以從平面圖族和 Wagner圖利用2-和與3-和的方法得到。

根據(jù)引理2.1和引理2.2,我們構(gòu)造出一個(gè)沒(méi)有K5-子式的圖,如圖3所示。

圖1 Wagner圖

圖2 平面圖

引理3.1[3]每一個(gè)平面圖都無(wú)圖5-可染。

圖3 沒(méi)有 K5-子式圖

3 定理1.1的證明

引理3.2 Wagner圖有一個(gè)無(wú)圈5-染色。

證明 令S={1,2,3,4,5}是一個(gè)5種的顏色集,根據(jù)圖1,可對(duì)Wagner圖進(jìn)行如下著色:點(diǎn)x染顏色1,點(diǎn)k染顏色2,點(diǎn)y染顏色3,點(diǎn)v染顏色4,點(diǎn)z染顏色5,w點(diǎn)可以染色1或2或4,不妨令w點(diǎn)染顏色2,點(diǎn)h可以染顏色3或4或5,于是h點(diǎn)染色3,最后,點(diǎn)u可以染顏色1或5,令u點(diǎn)染顏色1。

于是我們得到Wagner圖的一個(gè)5-染色,從圖1可知,Wagner圖的這個(gè)著色是無(wú)圈的。所以,Wagner圖是無(wú)圈5-可染的。

引理3.3[8]所有沒(méi)有K5子式的圖都5可選。假如一個(gè)圖是k-可選的,則它也是k-可染的。所以根據(jù)引理4.4.3,我們得到?jīng)]有K5-子式的圖都是5-可染的,下面的引理證明了沒(méi)有K5-子式的圖的這個(gè)5-染色是無(wú)圈的。

引理3.4 令圖G1是一個(gè)無(wú)圈5-可染的邊極大化平面圖,圖G2是一個(gè)Wagner圖,則從圖G1和G2利用2-和與3-和的方法得到的圖H有一個(gè)無(wú)圖5-染色。

證明 根據(jù)引理2.1和2.2,設(shè)L1是圖G1的一個(gè)無(wú)圈5-染色,L2是圖G2的一個(gè)無(wú)圈5-染色,L1′是極大化平面圖G1′的一個(gè)無(wú)圈5-染色, L2′是Wagner圖G2′的一個(gè)無(wú)圈5-染色。

(i)假如圖H是圖G1和圖G1′構(gòu)造出的平面圖(或是圖G2和圖G2′構(gòu)造出的圖),顯然可以使得L1和L1′在G1∩G1′中的顏色保持一致(或?qū)2和L2′可以使得在G2∩G2′中的顏色保持一致),則根據(jù)引理3.1和3.2,引理成立。

(ii)假如圖H是圖G1和圖G2構(gòu)造出的圖,顯然可以使得L1和L2在G1∩G2中的顏色保持一致。因此,我們可以定義L是圖H的一個(gè)5-染色,其中當(dāng)v∈V(G1),v∈V(G2)分別有L(v)=L1(v)和L2(v)=L2(v′)。下面需要證明圖H的染色L也是一個(gè)無(wú)圈染色。

假設(shè)染色L有圈,因此圖H有一個(gè)雙色圈C。但是由于L1和L2都是無(wú)圈染色,故雙色圈C不會(huì)單獨(dú)位于圖G1或者圖G2中。換句話(huà)說(shuō),圈C必須通過(guò)V(G1)∩V(G2)兩次。所以,|V(C)∩(V(G1)∩V(G2))|=2并且圈C在V(G1)∩V(G2)用兩種顏色。另一方面,假如雙色圈C包含V(G1)∩V(G2)的兩點(diǎn)x和y,則C1=xy∪(C∩G1)是圖G1的染色L1的一個(gè)雙色圈,矛盾。引理成立。

引理3.5 令圖G是一個(gè)無(wú)圈5-可染的邊極大化的沒(méi)有K5-子式的圖,圖W是一個(gè)Wagner圖或平面三角化圖,則從圖G和W利用2-和與3-和的方法得到的圖H有一個(gè)無(wú)圈5-染色。

證明 根據(jù)引理3.4,設(shè)L1是圖G的一個(gè)無(wú)圈5-染色,L2是圖W的一個(gè)無(wú)圈5-染色,顯然可以使得L1和L2在G∩W中的顏保持一致。因此,我們可以定義L是圖H的一個(gè)5-染色,其中當(dāng)v∈V(G),v∈V(W)分別有L(v)=L1(v)和L(v)=L2(v)。下面需要證明圖H的染色L也是一個(gè)無(wú)圈染色。

假設(shè)染色L有圈,因此圖H有一個(gè)雙色圈C。但是由于L1和L2都是無(wú)圈染色,故雙色圈C不會(huì)單獨(dú)位于圖G或者圖W中。換句話(huà)說(shuō),圈C必須通過(guò)V(G)∩V(W)兩次。所以,|V(C)∩(V (C)∩V(W))|=2并且圈C在V(G)∩V(W)用兩種顏色。另一方面,假如雙色圈C包含V(G)∩V(W)的兩點(diǎn)x和y,則C1=xy∪(C∩G)是圖G的染色L1的一個(gè)雙色圈,矛盾。

又根據(jù)引理2.1,任何一個(gè)沒(méi)有K5-子式的邊極大化圖都可以從平面三角化圖和Wagner圖通過(guò)K3和K2的傳遞被連續(xù)構(gòu)造。于是對(duì)每一次構(gòu)造都利用上面的方法,故引理成立。

由于每一個(gè)沒(méi)有K5-子式圖都是邊極大化的沒(méi)有K5-子式的圖的子圖,再根據(jù)引理3.4和3.5,定理1.1成立。

[1] M.O.A lbertson and D.M.Berman,Every p lanar graph has an acvlic 7-coloring,Iarael J.Math.1997,28:169-174.

[2] J.A.Bondy,U.S.R.M ury,Graph Theo ry,Grdute Texts M athematics.2008,244,Sp ringer.

[3] O.V.Borodin,On acyclic colo ring of p lanar graphs,Discrete M ath.2006,306:953-972.

[4] R.Diestel,Graph Theory,Sp ringer,New Yo rk,2000(electronicedition II).

[5] B.Grünbaum,Acyclic coloring of p lanar granhs,Iarael J. M ath.1973,14:390-408.

[6] Wenjie He,Wenjing M iao,Yufa Shen,Another p roof of the 5-choosability ofK5-minor-free graphs.Discrete Math, 2008,308:4024-4026.

[7] A.V.Kostochka,Acyclic 6-colorings of planar graphs(in Russian),Metody diskret.Analiz.1976,28:40-56.

[8] R.êkrekovski,Choosability ofK5-minor-free graphs,Discrete Math.1998,190:223-226.

[9] C.Thomassen,Every planar graph is 5-choosable,J. Gombin.Theory Ser.B.1994,62:180-181.

[10] K.Wagner,über eine Eigenschaft der ebenen Komplexe, Math,Ann.1937,144:570-590.

K5-m inor-free graphsare acyclically 5-colorable

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

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

In 2006,Borodin showed that all p lanar graphswere acyclically 5-colorable.In this paper the result is generalized to allK5-m ino r-free graphs.

Acyclic colorings;The wagner graph;K5-minor-free graphs;k-sum

O157

:A

1001-9383(2010)04-0001-03

2010-08-30

河北省自然科學(xué)基金資助項(xiàng)目(A 2006000004)

吳文文(1986-),男,山東臨沂人,研究生,研究方向:圖論.