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

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

沒有 K5-子式的圖是無圈5-可染的

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

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

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

無圈k-可染;Wagner圖;沒有K5-子式的圖;k-和

1 引言

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

定理1.1 所有沒有K5-子式的圖是無圖5-可染的

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

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

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

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

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

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

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

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

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

圖1 Wagner圖

圖2 平面圖

引理3.1[3]每一個平面圖都無圖5-可染。

圖3 沒有 K5-子式圖

3 定理1.1的證明

引理3.2 Wagner圖有一個無圈5-染色。

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

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

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

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

證明 根據(jù)引理2.1和2.2,設(shè)L1是圖G1的一個無圈5-染色,L2是圖G2的一個無圈5-染色,L1′是極大化平面圖G1′的一個無圈5-染色, L2′是Wagner圖G2′的一個無圈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的一個5-染色,其中當(dāng)v∈V(G1),v∈V(G2)分別有L(v)=L1(v)和L2(v)=L2(v′)。下面需要證明圖H的染色L也是一個無圈染色。

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

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

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

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

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

由于每一個沒有K5-子式圖都是邊極大化的沒有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é)基金資助項目(A 2006000004)

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