平面圖的3-可選性*

李曉艷,王應(yīng)前

(浙江師范大學(xué) 數(shù)理與信息工程學(xué)院,浙江 金華 321004)

?

平面圖的3-可選性*

李曉艷,王應(yīng)前

(浙江師范大學(xué) 數(shù)理與信息工程學(xué)院,浙江 金華 321004)

研究了特殊平面圖的3-可選性問(wèn)題.應(yīng)用經(jīng)典的權(quán)轉(zhuǎn)移方法,證明了不含4-,7-,9-圈且三角形的距離大于等于3的平面圖是3-可選的.這一結(jié)果進(jìn)一步拓展了平面圖的3-可選的充分條件.

平面圖;圈;距離;可選性

0 引 言

1979年,Erd?s 等[1]對(duì)2-可選問(wèn)題作了特征化的論述,并提出猜想：每一個(gè)平面圖是5-可選的,且存在非4-可選的平面圖.十多年以后,此猜想被證實(shí).Voigt[2]成功構(gòu)造出一個(gè)非4-可選的平面圖;Thomassen[3]證明了每一個(gè)平面圖是5-可選的.但是，能否判斷出一個(gè)給定的平面圖是3-或4-可選的問(wèn)題還未解決.1996年,Gutner[4]證明了這些問(wèn)題是NP-困難的.因此,研究平面圖是3-或4-可選的充分條件變得十分有意義.關(guān)于平面圖3-可選性的充分條件,總結(jié)如下:

定理1 平面圖是3-可選的,如果它不含奇圈[5];3-圈和4-圈[6];3-,5-和6-圈[7]; 3-,6-和7-圈[8];3-,7-和8-圈[9];3-,8-和9-圈[10-11];4-,5-,7-和9-圈[12];4-,5-,6-和9-圈[13];4-,6-,8-和9-圈[14];4-,7-,8-和9-圈[15];4-,6-,7-和9-圈[16];4-,5-,8-和9-圈[17];4-和5-圈,三角形距離大于等于4[18];4-,5-,6-圈,三角形距離大于等于3[18];5-,6-,7-圈,三角形距離大于等于3[19];5-,6-,8-圈,三角形距離大于等于2[19].

本文證明了以下結(jié)論:

定理2 不含4-,7-,9-圈且三角形的距離大于等于3的平面圖是3-可選的.

1 一些術(shù)語(yǔ)和記號(hào)

圖G是有限、簡(jiǎn)單、無(wú)向圖.若平面圖G=(V,E)能被嵌入一個(gè)平面使得邊僅在端點(diǎn)處相交,則稱(chēng)G是可平面的.可平面圖在平面內(nèi)的任何一個(gè)具體的使得邊僅在端點(diǎn)處相交的嵌入叫平面圖.對(duì)于平面圖G,用V,E,F和δ分別表示平面圖G的頂點(diǎn)集、邊集、面集和最小度.對(duì)任意的一個(gè)頂點(diǎn)v∈V,用d(v)表示v在G中的度數(shù),即與v關(guān)聯(lián)的邊的條數(shù).分別稱(chēng)度數(shù)為k、至少為k或至多為k的頂點(diǎn)為k-點(diǎn)、k+-點(diǎn)和k--點(diǎn).類(lèi)似可以定義k-面、k+-面和k--面.若2個(gè)圈(或2個(gè)面)至少共用一條邊,則稱(chēng)這2個(gè)圈(或2個(gè)面)相鄰.連接2個(gè)三角形的最短路的長(zhǎng)度稱(chēng)為三角形的距離.對(duì)于面f∈F,若v1,v2,…,vk是f上按某一時(shí)針?lè)较蜻B續(xù)出現(xiàn)的點(diǎn),則記f=[v1,v2,…,vk],且稱(chēng)f為一個(gè)(d(v1),d(v2),…,d(vk))-面.一個(gè)k-圈是一個(gè)長(zhǎng)度為k的圈,其大小記為d(f).3-圈又稱(chēng)為三角形.

若一個(gè)3-點(diǎn)v關(guān)聯(lián)1個(gè)3-面和2個(gè)10+-面,則稱(chēng)v是壞點(diǎn).若一個(gè)3-點(diǎn)v關(guān)聯(lián)1個(gè)3-面和1個(gè)5-面,則稱(chēng)v是半壞點(diǎn);此時(shí)的3-面稱(chēng)為壞面,5-面稱(chēng)為半壞面.若一個(gè)3-點(diǎn)v關(guān)聯(lián)2個(gè)5-面,則稱(chēng)v是弱點(diǎn).若一個(gè)3-點(diǎn)v關(guān)聯(lián)1個(gè)5-面和1個(gè)8+-面,則稱(chēng)v是半弱點(diǎn).否則,其他3-點(diǎn)v都是好點(diǎn).

2 定理 2 的證明

假設(shè)定理2不成立.設(shè)G為定理2的一個(gè)極小反例,也就是說(shuō)G是一個(gè)極小的非3-可選圖.設(shè)L是圖G的一個(gè)列表配置,其中|L(v)|=3(任意v∈V)使得G不是L-可染的.于是,G是連通的,不含4-,7-,9-圈,有以下引理：

引理1[17,19]1)δ(G)≥3;

2)三角形的距離大于等于3;

3)3-面與6-面不相鄰,3-面與8-面不相鄰，5-面與6-面不相鄰;

4)設(shè)v是G中的一個(gè)3-點(diǎn),若v同時(shí)關(guān)聯(lián)1個(gè)3-面和1個(gè)5-面,則剩下的1個(gè)與之相關(guān)聯(lián)的面是10+-面;

5)設(shè)v是G中的一個(gè)3-點(diǎn),若v同時(shí)關(guān)聯(lián)2個(gè)5-面,則剩下的1個(gè)與之相關(guān)聯(lián)的面是8+-面;

6)無(wú)弦偶圈至少有1個(gè)4+-點(diǎn).

下面運(yùn)用權(quán)轉(zhuǎn)移方法完成定理2的證明.

權(quán)轉(zhuǎn)移規(guī)則定義如下:

R1:轉(zhuǎn)給3-點(diǎn)的權(quán).

R1.1:若v是一個(gè)好點(diǎn),則v從3個(gè)6+-面各得權(quán) 1.

R2:轉(zhuǎn)給 4-點(diǎn)的權(quán).設(shè)頂點(diǎn)v關(guān)聯(lián)的面依順時(shí)針排列為 f1,f2,f3,f4.

R2.2:設(shè)v是關(guān)聯(lián)三角形的4-點(diǎn).由引理1中的2)知,v至多關(guān)聯(lián)1個(gè)三角形.

R2.3:設(shè)v是不關(guān)聯(lián)三角形、但關(guān)聯(lián)5-面的4-點(diǎn).

現(xiàn)在檢驗(yàn)?x∈V∪F,有ch′(v)≥0.先檢驗(yàn)面的最終權(quán).注意到d(f)≠4,7,9.

當(dāng)d(f)=3時(shí),由權(quán)轉(zhuǎn)移規(guī)則知,沒(méi)有權(quán)轉(zhuǎn)入和轉(zhuǎn)出,所以ch′(f)=ch(f)=0.

當(dāng)d(f)=6時(shí),由引理1中的3)知,f不與3-面相鄰,且 f不與5-面相鄰;由引理1中的6)知,f至少有1個(gè)4+-點(diǎn).因此，由R1.1,R2.1,R2.2.2和R2.3.2知,ch′(f)≥2d(f)-6-6×1=0.

當(dāng)d(f)=8 時(shí),由引理1中的3)知,f不與3-面相鄰.由引理1中的6)知,f至少有一個(gè)4+-點(diǎn).

當(dāng)d(f)=10時(shí),設(shè) f=[v1v2…v10]是一個(gè)10-面.由引理1中的2)和引理1中的6) 知,T(f)≤2,至少有1 個(gè) 4+-點(diǎn);若 T(f)=2,則由對(duì)稱(chēng)性,根據(jù)3-面的位置可分為2類(lèi):

1)v1v2和v6v7各關(guān)聯(lián)1個(gè)3-面.根據(jù)4+-點(diǎn)所在位置可分為3類(lèi):

①當(dāng)4+-點(diǎn)在壞面上時(shí),由引理1中的3)～5),R1和R2 知,

②當(dāng)4+-點(diǎn)在半壞面上時(shí),由引理1中的3)～5),R1和R2 知,

2)v1v2和v5v6各關(guān)聯(lián)1個(gè)3-面.根據(jù)4+-點(diǎn)所在位置可分為3類(lèi):

②當(dāng)4+-點(diǎn)在半壞面上時(shí),由引理1中的3)～5),R1和R2知,

③當(dāng)4+-點(diǎn)既不在壞面上,也不在半壞面上時(shí),由引理1中的3)～5),R1和R2知,

若T(f)≤1,則由引理1中的3)～5),R1和R2知,

當(dāng)d(f)=11時(shí),設(shè) f=[v1v2…v11]是一個(gè)11-面.由引理1中的2)知,T(f)≤2;當(dāng)T(f)=2時(shí),由對(duì)稱(chēng)性,根據(jù)3-面的位置可分為2類(lèi):

1)v1v2和v6v7各關(guān)聯(lián)1個(gè)3-面.由引理1中的2)～5)和R1知,若v4關(guān)聯(lián)5-面,則

2)v1v2和v5v6各關(guān)聯(lián)1個(gè)3-面.由引理1中的2)～5)和R1知,

當(dāng)T(f)≤1時(shí),由引理1中的2)～5)和R1知,

檢驗(yàn)點(diǎn)的最終權(quán).

由引理1中的1)～2)知,d(v)≥3且v至多關(guān)聯(lián)1個(gè)三角形.

當(dāng)d(v)≥6時(shí),由權(quán)轉(zhuǎn)移規(guī)則知,ch′(v)=d(v)-6≥0.定理 2 證畢.

[1]Erd?s P,Rubin A L,Taylor H.Choosability in graphs[J].Congr Numer,1979,26:125-157.

[2]Voigt M.List colourings of planar graphs[J].Discrete Math,1993,120(1/2/3):215-219.

[3]Thomassen C.Every planar graph is 5-choosable[J].J Combin Theory Ser B,1994,62(1):180-181.

[4]Gutner S.The complexity of planar graph choosability[J].Discrete Math,1996,159(1):119-130.

[5]Alon N,Tarsi M.Colorings and orientations of graphs[J].Combinatorica,1992,12(2):125-134.

[6]Thomassen C.3-list coloring planar graphs of girth 5[J].J Combin Theory Ser B,1995,64(1):101-107.

[7]Lam P,Shiu W C,Song Z M.The 3-choosability of plane graphs of girth 4[J].Discrete Math,2005,294(3):297-301.

[10]Zhang H,Xu B,Sun Z.Every plane graph with girth at least 4 without 8- and 9-circuits is 3-choosable[J].Ars Comb,2006,80:247-257.

[11]Zhu X,Miao L,Wang C.On 3-choosability of plane graphs without 3-,8- and 9-cycles[J].Australas J Comb,2007,38:249-254.

[12]Zhang L,Wu B.Three-coloring planar graphs without certain small cycles[J].Graph Theory Notes of New York,2004,46:27-30.

[13]Zhang L,Wu B.A note on 3-choosability of planar graphs without certain cycles[J].Discrete Math,2005,297(1/2/3):206-209.

[14]Shen L,Wang Y.A sufficient condition for a planar graph to be 3-choosable[J].Inform Process Lett,2007,104(4):146-151.

[15]Wang Y,Shen L.Planar graphs without cycles of length 4,7,8,or 9 are 3-choosable[J].Discrete Math,2010,159(4):232-239.

[16]Wang Y,Lu H,Chen M.A note on 3-choosability of planar graphs[J].Inform Process Lett,2008,105(5):206-211.

[17]Wang Y,Chen L.Planar graphs without cycles of length 4,5,8,or 9 are 3-choosable[J].Discrete Math,2010,310(1):147-158.

[18]Montassier M,Raspaud A,Wang Weifan.Bordeaux 3-color conjecture and 3-choosability[J].Discrete Math,2006,306(6):573-579.

[19]Zhang H,Sun Z.On 3-choosability of planar graphs without certain cycles[J].Inform Process Lett,2008,107(3/4):102-106.

(責(zé)任編輯 陶立方)

A note on 3-choosability of planar graphs

LI Xiaoyan,WANG Yingqian

(CollegeofMathematics,PhysicsandInformationEngineering,ZhejiangNormalUniversity,Jinhua321004,China)

The problem of special planar graphs of 3-choosability was studied.According to the discharging,it was showed that planar graphs with neither 4-,7-,9-cycles nor triangles of distance less than 3 were 3-choosable.The result generalized the sufficient condition for the planar graphs of 3-choosability.

planargraph; cycles; distance; choosability

10.16218/j.issn.1001-5051.2016.01.003

??2014-10-08；

2015-09-07

國(guó)家自然科學(xué)基金資助項(xiàng)目(11271335)

李曉艷(1990-),女，河南滑縣人,碩士研究生.研究方向:運(yùn)籌學(xué)與控制論.

O157.5

A

1001-5051(2016)01-013-05