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

朱曉穎

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

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

朱曉穎

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

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

可選擇的;平面圖;圍長

1 引言

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

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

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

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

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

本文證明了每個圍長至少為4且無8-,9-和10-圈的平面圖是3-選擇的.

2 基本引理

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

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

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

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

3 結(jié)論

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

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

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

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

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

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

圖1 f是42-面時

圖2 f是41-面時

由上述討論,面f通過邊uv轉(zhuǎn)移的權(quán)值是小于或等于被調(diào)整后的定額數(shù)值,到這里證明了φ?(f)≥0對于所有的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)于無6-,8-和9-圈平面圖的3-選色[J].南京師范大學(xué)報,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