没有 K5-子式的图是无圈5-可染的

吴文文,何义杰,黄大江,魏立鹏

(河北工业大学理学院应用数学研究所,天津 300130)

没有 K5-子式的图是无圈5-可染的

吴文文,何义杰,黄大江,魏立鹏

(河北工业大学理学院应用数学研究所,天津 300130)

2006年,Borodin证明了所有平面图都可以无圈5-可染。本文推广Borodin的结果到没有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]也用另一种方法证明了这个结果。本文根据O.V.Borodin[3]的平面图无圈5-可染性,以及无K5-子式图的构造,证明所有没有K5-子式的图也可以无圈5-可染。

定理1.1 所有没有K5-子式的图是无图5-可染的

在开始进行证明定理1.1之前,本文需要一些概念和定义。

本文中提到的所有图都是简单,有限且无向的。长度为k的圈称为k-圈,由两种颜色的顶点导出的圈称为双色圈。图G的k染色是指k种颜色对图G所有点进行染色。一个正常的k染色是指图G的一个k染色,并且使得任意相邻两个点染不同颜色。图G是无圈k-可染的是指图G有一个正常的k染色,同时使得由两种染色的点导出的子图没有双色圈。

图H称为图G的一个子式(minor),如果图H(或者与H同构的图)可以由图G通过一系列的边收缩,边删除或顶点删除(按任何顺序)而获得。图G被称为没有H-子式图当且仅当它没有图H作为一个子式。一个图如果可以画在一个平面上并且使得它的所有边仅在端点处相交,则认为它嵌入在平面或者是平面图。这样的一个画法被称为图的一个平面嵌入。一个平面图是三角化图当且仅当它的每一个面的边界是一个3-圈。

Wagner图(如图1)是一个带有8个点和12条边的3-正则图。它是带有8个点的 Möbius ladder图。作为一个 Möbius ladder,Wagner图是没有K5-子式,但是有K3,3-子式的非平面图。

假设图G1和图G2是个k点的完全图。由G1∪G2删除G1∩G2的边得到的图叫做G1和G2的k-和(见文献[2]275页)。

2 构造没有K5-子式的图

引理2.1(Wagner定理[10,4])令图G是一个没有K5-子式的边极大化图。假如|G|≥4,则图G可以从平面三角画图和Wagner图通过K3和K2的传递被连续构造。

引理2.2 任何一个没有K5-子式的2-连通的图可以从平面图族和 Wagner图利用2-和与3-和的方法得到。

根据引理2.1和引理2.2,我们构造出一个没有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种的颜色集,根据图1,可对Wagner图进行如下着色:点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-可染的。所以根据引理4.4.3,我们得到没有K5-子式的图都是5-可染的,下面的引理证明了没有K5-子式的图的这个5-染色是无圈的。

引理3.4 令图G1是一个无圈5-可染的边极大化平面图,图G2是一个Wagner图,则从图G1和G2利用2-和与3-和的方法得到的图H有一个无图5-染色。

证明 根据引理2.1和2.2,设L1是图G1的一个无圈5-染色,L2是图G2的一个无圈5-染色,L1′是极大化平面图G1′的一个无圈5-染色, L2′是Wagner图G2′的一个无圈5-染色。

(i)假如图H是图G1和图G1′构造出的平面图(或是图G2和图G2′构造出的图),显然可以使得L1和L1′在G1∩G1′中的颜色保持一致(或对L2和L2′可以使得在G2∩G2′中的颜色保持一致),则根据引理3.1和3.2,引理成立。

(ii)假如图H是图G1和图G2构造出的图,显然可以使得L1和L2在G1∩G2中的颜色保持一致。因此,我们可以定义L是图H的一个5-染色,其中当v∈V(G1),v∈V(G2)分别有L(v)=L1(v)和L2(v)=L2(v′)。下面需要证明图H的染色L也是一个无圈染色。

假设染色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-染色。

证明 根据引理3.4,设L1是图G的一个无圈5-染色,L2是图W的一个无圈5-染色,显然可以使得L1和L2在G∩W中的颜保持一致。因此,我们可以定义L是图H的一个5-染色,其中当v∈V(G),v∈V(W)分别有L(v)=L1(v)和L(v)=L2(v)。下面需要证明图H的染色L也是一个无圈染色。

假设染色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的一个双色圈,矛盾。

又根据引理2.1,任何一个没有K5-子式的边极大化图都可以从平面三角化图和Wagner图通过K3和K2的传递被连续构造。于是对每一次构造都利用上面的方法,故引理成立。

由于每一个没有K5-子式图都是边极大化的没有K5-子式的图的子图,再根据引理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

河北省自然科学基金资助项目(A 2006000004)

吴文文(1986-),男,山东临沂人,研究生,研究方向:图论.