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

朱曉穎

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

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

朱曉穎

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

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

可選擇的;平面圖;圍長

1 引言

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

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

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

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

關于2-可選色的圖,文獻[2]作了特征化的論述.文獻[3]證明了每個平面圖是5-可選色的,且文獻[4]證明了每個圍長至少為5的平面圖是3-可選擇的.文獻[5]構造了一個圍長是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是一個長度為偶數的圈,則G是2-可選擇的.

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

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

3 結論

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

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

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

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

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

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

圖1 f是42-面時

圖2 f是41-面時

由上述討論,面f通過邊uv轉移的權值是小于或等于被調整后的定額數值,到這里證明了φ?(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]張海輝,沈邦玉.關于無6-,8-和9-圈平面圖的3-選色[J].南京師范大學報,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-),碩士,講師,研究方向：圖論及其應用.

2010 MSC:05C78