平面圖的非正常染色*

張傳妮, 王應(yīng)前

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

平面圖的非正常染色*

張傳妮, 王應(yīng)前

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

研究了特殊平面圖的非正常染色問題.應(yīng)用經(jīng)典的權(quán)轉(zhuǎn)移方法,證明了4-圈不與3-,4-圈相鄰且不含7-圈的平面圖是(1,1,0)-可染的.這一結(jié)果進(jìn)一步拓展了平面圖的非正常可染的充分條件.

平面圖;圈;權(quán)轉(zhuǎn)移;非正常染色

0 引 言

自從四色猜想成為四色定理[1-2](每個平面圖是4色可染的)之后,Steinberg猜想[3](每個既沒有4-圈又沒有5-圈的平面圖是3色可染的)便成為圖染色理論中的一個焦點.為解決這一具極強(qiáng)挑戰(zhàn)性的猜想,許多學(xué)者[4-6]作出了諸多努力,并在多方面推廣了圖的經(jīng)典染色.圖的非正常染色(或缺陷染色)便是推廣之一.更準(zhǔn)確地說,設(shè)d1,d2,…,dk是k個非負(fù)整數(shù),G=(V,E)是一個圖,若可以用k個色,譬如,c1,c2,…,ck,去染G的頂點,使得每個染色ci的頂點至多有di個鄰點染有同樣的色(i=1,2,…,k),則稱G是非正常(d1,d2,…,dk)-可染的,簡稱為(d1,d2,…,dk)-可染的.運用這一術(shù)語,四色定理可改述為“每個平面圖是(0,0,0,0)-可染的”,Steinberg猜想可改述為“每個既沒有4-圈又沒有5-圈的平面圖是(0,0,0)-可染的”.圖的非正常染色已得到廣泛研究,并已得到許多有趣的結(jié)果.例如:

每個平面圖是(2,2,2)-可染的[7];

每個既不含5-圈又不含相鄰三角形的平面圖是(1,1,1)-可染的[8].

從非正常染色角度研究Steinberg猜想所取得的最好結(jié)果可總結(jié)為下面的定理:

定理1 每個既沒有4-圈又沒有5-圈的平面圖是:

1)(列表)(1,1,1)-可染的[4];

2)(3,0,0)-可染的[5];

3)(1,1,0)-可染的[9-10];

4)(2,0,0)-可染的[6].

由于Vincent Cohen-Addad等[11]最近證明了Steinberg猜想是錯誤的,因此提出如下更一般的猜想就顯得更有研究意義.

推廣的Steinberg猜想:對于l∈{6,7,8,9},既不含4-圈又不含l-圈的平面圖是(0,0,0)-可染的.

同樣,從非正常的角度研究此猜想所取得的最好結(jié)果,以及對最好結(jié)果作出的進(jìn)一步改進(jìn),可總結(jié)為下面的定理:

定理2 每個既沒有4-圈又沒有l(wèi)-圈的平面圖是:

1)(3,0,0)-和(1,1,0)-可染的[12];(2,0,0)-可染的[13],其中l(wèi)=6;

2)(2,0,0)-可染的[14]和(1,1,0)-可染的[15],其中l(wèi)=7;

3)(1,1,0)-可染的[15],其中l(wèi)=8;

4)4-圈不與3-圈相鄰且不含6-圈的平面圖是(1,1,0)-可染的[16].

鑒于不含6-圈的平面圖可推出4-面不與4-面相鄰的結(jié)論,為此本文將證明如下結(jié)果:

定理3 4-圈不與3-,4-圈相鄰且不含7-圈的平面圖是(1,1,0)-可染的.

1 一些術(shù)語和記號

設(shè)圖G是有限、簡單、無向圖.一個平面圖是指一個可平面圖在平面內(nèi)的一個嵌入.對于平面圖G,用V,E,F和δ分別表示平面圖G的頂點集、邊集、面集和最小度.對任意的一個頂點v∈V,用d(v)表示v在G中的度數(shù),即與v關(guān)聯(lián)的邊的條數(shù).若d(v)=k(d(v)≥k或d(v)≤k),則稱v是一個k-點(k+-點或k--點).稱邊xy∈E為(d(x),d(y))-邊,且x是y的d(x)-鄰點.對于一個面f∈F,用d(f)表示f的邊界的長度,稱為面f的長度.上述有關(guān)點的概念對于面或圈同樣適用.若v1,v2,…,vk是f上按某一時針方向連續(xù)出現(xiàn)的點,則記f=[v1,v2,…,vk],且稱f為一個(d(v1),d(v2),…,d(vk))-面.3-圈又稱為三角形.若一個點(或一條邊)與一個三角形相關(guān)聯(lián),則稱該點(或該邊)是三角的.若uv∈E,且uv是非三角的,則稱u是v的一個孤立鄰點,否則是非孤立鄰點.若一個3-點v關(guān)聯(lián)一個3-面f,則稱v的不與3-面相關(guān)聯(lián)的那個鄰點v′為v或f的外d(v′)-鄰點,且稱f是v′的一個懸掛3-面.若點v恰關(guān)聯(lián)k個不相鄰的三角形,則稱v是k-三角的.若2個圈(或2個面)至少共用一條邊(點),則稱這2個圈(或2個面)相鄰(相交).

若一個4-點v關(guān)聯(lián)1個(4,4,4)-面且有2個孤立3-鄰點,則稱v是輕的,記為4l-點.

若一個4-點v關(guān)聯(lián)1個 (3,4,5+)-面且有2個孤立3-鄰點,則稱v是弱的,記為4w-點;

若一個5-點v關(guān)聯(lián)1個(3,4,5)-面和1個(3,4w,5)-面,則稱v是1-壞的,記為5b-點.

若一個5-點v關(guān)聯(lián)1個(3,5,5+)-面和1個(3,4w,5)-面且有1個孤立3-點,則稱v是2-壞的,記為5bb-點.

2 定理3的證明

假設(shè)定理3不真.設(shè)G=(V,E,F)為定理3的一個頂點最少的反例,也就是說G本身不是(1,1,0)-可染圖,但G的任意一個正常的點導(dǎo)出子圖G′有一個(1,1,0)-染色φ,則G有以下結(jié)構(gòu)性質(zhì)：

引理1[9-10]1)δ(G)≥3;

2)G中的3-點至多有1個3-鄰點;

3)若3-面f=[uvw]中d(u)=d(v)=3,則d(w)≥5;

4)若3-點v關(guān)聯(lián)1個(3,4,4)-面,則v的外鄰點是4+-點;

5)4-點至少有1個4+-鄰點;

6)關(guān)聯(lián)1個(3,4,4)-面的1-三角4-點至少有1個孤立4+-鄰點;

7)關(guān)聯(lián)1個(3,4,4)-面的2-三角4-點的另一個3-面不是(4,4-,4-)-面.

引理2[15]若5-點v關(guān)聯(lián)2個3-面T1=[v1v2v]和T2=[v3v4v]且第5個鄰點為v5,則

1)T1,T2中至少有1個不是(3,3,5)-面;

2)若d(v5)=3,則T1,T2中至少有1個不是(3,4-,5)-面;

3)若T1是(3,3,5)-面,T2是(3,4,5)-面且d(v3)=3,則v3的外鄰點是4+-點;

4)若T1,T2均是(3,4,5)-面且d(v1)=d(v2)=3,則v1和v3的外鄰點至少有1個是4+-點;

5)T1,T2中至少有1個不是(3,4w,5)-面;

6)若T1是(3,3,5)-面,則T2不是(3,4w,5)-面;

7)若T1是(3,4,5)-面且d(v1)=3,T2是(3,4w,5)-面,則v1的外鄰點是4+-點.

引理3[15]1)G中無(4l,4l,4)-面.

2)G中無(3,5bb,5bb)-面.

3)①G中4--圈不與4--圈相鄰,3-面不與6-面相鄰且4-面不與5-面相鄰(即4-面必與6+-面相鄰);

②若3-點v關(guān)聯(lián)3個3-面f1,f2和f3且d(f1)=3,d(f2)=5,則d(f3)≥8;

③G中5-面至多與1個3-面相鄰.

3 權(quán)轉(zhuǎn)移

為完成定理3的證明,下面將運用權(quán)轉(zhuǎn)移方法導(dǎo)出矛盾.

先假設(shè)定理3的關(guān)于點數(shù)極小的一個反例G=(V,E,F)是2-連通的,即G中每個面的邊界是一個圈,G中每個點v關(guān)聯(lián)d(v)個不同的面.定義初始權(quán)為ch(x)=d(x)-4,?x∈V∪F.

設(shè)最終權(quán)函數(shù)為ch′(x).若能定義適當(dāng)?shù)臋?quán)轉(zhuǎn)移規(guī)則,重新分配點和面的權(quán),使得對任意的x∈V∪F,有ch′(x)≥0,進(jìn)而有

從而得到矛盾.這就證明了當(dāng)G是2-連通時,定理3成立.

若一個4-點v關(guān)聯(lián)1個(3,4,4)-面和3個5-面且有1個孤立3-鄰點(根據(jù)引理1中的6)知,v至多有1個孤立3-鄰點),則稱v是壞的,記為4b-點.

根據(jù)4b-點的定義及G無7-圈,易得G無(3,4b,4b)-面.

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

R1:5+-面轉(zhuǎn)出的權(quán):

R2:轉(zhuǎn)給3-點v的權(quán):

R2.2:設(shè)v不關(guān)聯(lián)3-面,則v先根據(jù)R1從它關(guān)聯(lián)的3個面得權(quán),再平均地從它的4+-鄰點得權(quán),使得 ch′(v)=0.

R3:轉(zhuǎn)給3-面 f=[v1v2v3]的權(quán)(其中d(v1)≤d(v2)≤d(v3)):

現(xiàn)在檢驗?x∈V∪F的新權(quán)ch′(x)≥0.

先檢驗面的最終權(quán).注意到d(f)≠7.

當(dāng)d(f)≥8時,由R1.1知,

當(dāng)d(f)=6時,由R1.2知,

當(dāng)d(f)=5時,由R1.3知,

當(dāng)d(f)=4時, f的權(quán)無轉(zhuǎn)移,故ch′(f)=ch(f).

當(dāng)d(f)=3時,設(shè) f=[v1v2v3]且d(v1)≤d(v2)≤d(v3).由引理1中的1)知,d(v1)≥3.

[1]Appel K,Haken W.Every planar map is four colorable,I:Discharging[J].Illinois J Math,1977,21(3):429-490.

[2]Appel K,Haken W,Koch J.Every planar map is four colorable,II:Reducibility[J].Illinois J Math,1977,21(3):491-567.

[3]Steinberg R.The state of the three color problem[J].Ann Diserete Math,1993,55(8):211-248.

[4]Lih K,Song Z,Wang W,et al.A note on list improper coloring planar graphs[J].Appl Math Lett,2001,14(3):269-273.

[5]Hill O,Smith D,Wang Yingqian,et al.Planar graphs without cycles of length 4 or 5 are (3,0,0)-colorable[J].Discrete Math,2013,313(20):2312-2317.

[6]Chen M,Wang Y,Liu P,et al.Planar graphs without cycles of length 4 or 5 are (2,0,0)-colorable[J].Discrete Math,2016,339(2):886-905.

[7]Cowen L J,Cowen R H,Woodall D R.Defective colorings of graphs in surfaces:Partitions into subgraphs of bounded valency[J].J Graph Theory,1986,10(2):187-195.

[8]Xu Baogang.On (3,1)*-coloring of plane graphs[J].SIAM J Discrete Math,2009,23(1):205-220.

[9]Xu Lingji,Miao Zhengke,Wang Yingqian.Planar graphs with cycles of length neither 4 nor 5 are (1,1,0)-colorable[J].J Comb Optim,2014,28(4):774-786.

[10]Hill O,Yu Gexin.A relaxation of Steinberg′s conjecture[J].SIAM J Discrete Math,2013,27(1):584-596.

[11]Cohen-Addad V,Hebdige M,Krl D,et al.Steinberg′s conjecture is false[J].J Combin Theory Ser B,2016,122:452-456.

[12]徐靈姬,王應(yīng)前.既不含4-圈又不含6-圈的平面圖的非正常染色[J].中國科學(xué):A輯 數(shù)學(xué),2013,43(1):15-24.

[13]Wang Yingqian,Xu Jinghan.Planar graphs with cycles of length neither 4 nor 6 are (2,0,0)-colorable[J].Inform Process Lett,2013,113(18):659-663.

[14]Liu Peipei,Wang Yingqian.Planar graphs without cycles of length 4 or 7 are (2,0,0)-colorable (in Chinese)[J].Sci Sin Math,2014,44(11):1153-1164.

[15]Wang Yingqian,Xu Jinghan.Improper colorability of planar graphs without prescribed short cycles[J].Discrete Math,2014,322:5-14.

[16]Bai Ying,Li Xiangwen,Yu Gexin.Every planar graph without 3-cycles adjacent to 4-cycles and without 6-cycles is (1,1,0)-colorable[J].J Comb Optim,2017,33(4):1354-1364.

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

A note on improper colorability of planar graphs

ZHANG Chuanni, WANG Yingqian

(CollegeofMathematics,PhysicsandInformationEngineering,ZhejiangNormalUniversity,Jinhua321004,China)

The problem of special planar graphs of improper colorability was studied. By the discharging, it was showed that every planar graph without 4-cycles adjacent to 3-cycles or 4-cycles and without 7-cycles was (1,1,0)-colorable.The result generalized the sufficient condition for the planar graphs of improper colorability.

planar graph; cycles; discharging; improper colorability

10.16218/j.issn.1001-5051.2017.03.004

?2016-06-16；

2016-10-17

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

張傳妮(1988-),女，山東臨沂人，碩士研究生.研究方向：運籌學(xué)與控制論.>

O157.5

A

1001-5051(2017)03-0267-08