無(wú)8-,9-和10-圈的平面圖的3-可選擇性

朱曉穎

(南京航空航天大學(xué)金城學(xué)院,江蘇南京 211156)

無(wú)8-,9-和10-圈的平面圖的3-可選擇性

朱曉穎

(南京航空航天大學(xué)金城學(xué)院,江蘇南京 211156)

尋找平面圖是3-或者4-可選擇的充分條件是圖的染色理論中一個(gè)重要研究課題,本文研究了圍長(zhǎng)至少是4的特殊平面圖的選擇數(shù),通過(guò)權(quán)轉(zhuǎn)移的方法證明了每個(gè)圍長(zhǎng)至少是4且不含8-圈,9-圈和10-圈的平面圖是3-可選擇的.

可選擇的;平面圖;圍長(zhǎng)

1 引言

本文中所考慮的圖都是有限、簡(jiǎn)單的平面圖,未定義的符號(hào)可參照文獻(xiàn)[1].G=(V,E,F)表示一個(gè)平面圖,V,E,F分別為其頂點(diǎn)集,邊集和面集.NG(v)表示與頂點(diǎn)相鄰的頂點(diǎn)集合,即頂點(diǎn)v的鄰域.一個(gè)頂點(diǎn)的度

若d(v)=k,則稱v是一個(gè)k-頂點(diǎn),δ(G)為圖中頂點(diǎn)的最小度.與f關(guān)聯(lián)的邊的數(shù)目(割邊按兩次算)記為面f的度數(shù),記作d(f).若d(f)=k,則稱f是一個(gè)k-面.設(shè)k是個(gè)整數(shù),k+和k-分別表示大于等于k和小于等于k的整數(shù).G中所有長(zhǎng)為k的圈組成的集合記為Ck.若Ck=?,則稱圖G是Ck-free.G中最短圈的長(zhǎng)度稱為G的圍長(zhǎng).若兩個(gè)面至少有一條公共邊,則這兩個(gè)面稱為是相鄰的.

定義1.1若與一個(gè)h-面相關(guān)聯(lián)的所有頂點(diǎn)均為3--頂點(diǎn),則稱這個(gè)h-面為light h-面,否則如果它至少和一個(gè)4+-頂點(diǎn)相關(guān)聯(lián),則稱它為non-light h-面.若f是一個(gè)non-light h-面,且b(f)上除了一個(gè)4+度點(diǎn)外,其余點(diǎn)均為3--頂點(diǎn),則稱此h-面為minimal h-面,否則,若h-面至少與兩個(gè)4+-頂點(diǎn)相關(guān)聯(lián),則稱此h-面為non-minimal h-面.

定義1.2對(duì)G中每個(gè)頂點(diǎn)v都分配一個(gè)顏色列表L(v),使得每個(gè)頂點(diǎn)能從其關(guān)聯(lián)的色表中選色并且相鄰的兩個(gè)頂點(diǎn)選擇不同的顏色,稱為G的一個(gè)L-著色.若對(duì)圖G的每個(gè)頂點(diǎn)的列表滿足圖G總存在L-著色,則稱圖G是k-可選擇的.定義使得圖G是k-可選擇的最小的自然數(shù)k稱為圖G的選擇數(shù)(或選色數(shù)),記為ch(G).

關(guān)于2-可選色的圖,文獻(xiàn)[2]作了特征化的論述.文獻(xiàn)[3]證明了每個(gè)平面圖是5-可選色的,且文獻(xiàn)[4]證明了每個(gè)圍長(zhǎng)至少為5的平面圖是3-可選擇的.文獻(xiàn)[5]構(gòu)造了一個(gè)圍長(zhǎng)是4但不是3-可選擇的圖,因此要對(duì)3-可選擇的平面圖的特征還需進(jìn)一步刻畫(huà),必須尋找一些條件,使得某一類平面圖是3-可選擇的.文獻(xiàn)[6]論證了圍長(zhǎng)至少為4且無(wú)5-和6-圈的平面圖是3-可選擇的.文獻(xiàn)[7-8]中論證了任何圍長(zhǎng)至少為4且無(wú)6-,8-和9-圈的平面圖都是3-可選擇的以及圍長(zhǎng)至少為4且無(wú)5-,8-和9-圈的平面圖都是3-可選擇的.

本文證明了每個(gè)圍長(zhǎng)至少為4且無(wú)8-,9-和10-圈的平面圖是3-選擇的.

2 基本引理

在證明定理之前,首先給出以下的三個(gè)引理:

引理2.1[9]若G是一個(gè)長(zhǎng)度為偶數(shù)的圈,則G是2-可選擇的.

引理2.2[7]若G是一個(gè)非-3-可選擇圖,且G的每一個(gè)非空真子集V??V的導(dǎo)出子圖G[V?]是3-可選擇的,則G的任何一個(gè)長(zhǎng)度為偶數(shù)的圈至少含有一個(gè)4+-頂點(diǎn).

引理2.3[8]若G是一個(gè)非-3-可選擇圖,且G的每一個(gè)非空真子集V??V的導(dǎo)出子圖G[V?]是3-可選擇的,若C1和C2是圖中兩個(gè)恰有一個(gè)公共頂點(diǎn)的4-圈,則C1和C2中至少有一個(gè)是non-minimal圈.

3 結(jié)論

由于考慮的圖G不含長(zhǎng)度為8-,9-和10-的圈,可得G具有下列性質(zhì):

(O1)一個(gè)4-面至多能和兩個(gè)相鄰的4-面相鄰;

(O2)一個(gè)4-面不能和另一個(gè)6-面相鄰;也不能和另一個(gè)7-面相鄰;

(O3)一個(gè)5-面至多與兩個(gè)4-面相鄰;

(O4)一個(gè)5-面不能和另一個(gè)5-面相鄰,也不能和另一個(gè)6-面或7-面相鄰.

用權(quán)轉(zhuǎn)移的方法調(diào)整所有的點(diǎn)和面的權(quán)值,調(diào)整后的權(quán)函數(shù)記為φ?(x),若權(quán)的移動(dòng)導(dǎo)致對(duì)所有的x∈V∪F,φ?(x)≥0,則得到矛盾,從而完成定理的證明.當(dāng)一個(gè)4-面f與i個(gè)4-面相鄰時(shí),稱該4-面f為4i-面,其中i為0,1,2.權(quán)的移動(dòng)根據(jù)以下規(guī)則:

圖1 f是42-面時(shí)

圖2 f是41-面時(shí)

由上述討論,面f通過(guò)邊uv轉(zhuǎn)移的權(quán)值是小于或等于被調(diào)整后的定額數(shù)值,到這里證明了φ?(f)≥0對(duì)于所有的x∈V∪F,所以有

得出矛盾,得證.

[1]Bondy J A,Murty U S R.Graph Theory with Applications[M].New Youk:Macmillan Co.,1976.

[2]Erdos P,Rubin A L,Taylor H.Choosability in graphs[J].Congr.Numer.,1979,26:125-157.

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

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

[5]Voigt M.List colouring of planar graphs[J].Discrete Math.,1993,120:215-219.

[6]Peter C B Lam.The 3-choosability of plane graphs of girth 4[J].Discrete Math.,2005,294:297-301.

[7]張海輝,沈邦玉.關(guān)于無(wú)6-,8-和9-圈平面圖的3-選色[J].南京師范大學(xué)報(bào),2004,27:55-60.

[8]Zhang Haihui.On 3-choosability of plane graphs without 5-,8-and 9-cycles[J].Journal of Lanzhou University: Natural Sciences,2005,41:93-97.

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

The 3-choosability of plane graphs without 8-,9-and 10-cycles

Zhu Xiaoying
(College of Jincheng,Nanjing University of Aeronautics and Astronautics,Nanjing211156,China)

An important researth on coloring of planar graphs is to determine whether a given planar graphs is 3-choosable or 4-choosable.In this paper,we study the choice number of special planers with girth at least 4. According to the discharging method,it is shown that every planar graph with girth at least 4 and without 8-, 9-and 10-cycles is 3-choosable.

choosability,plane graph,girth

O157.5

A

1008-5513(2013)06-0609-06

10.3969/j.issn.1008-5513.2013.06.009

2013-07-17.

朱曉穎(1979-),碩士,講師,研究方向：圖論及其應(yīng)用.

2010 MSC:05C78