平面图的3-可选性*

李晓艳,王应前

(浙江师范大学 数理与信息工程学院,浙江 金华 321004)



平面图的3-可选性*

李晓艳,王应前

(浙江师范大学 数理与信息工程学院,浙江 金华 321004)

研究了特殊平面图的3-可选性问题.应用经典的权转移方法,证明了不含4-,7-,9-圈且三角形的距离大于等于3的平面图是3-可选的.这一结果进一步拓展了平面图的3-可选的充分条件.

平面图;圈;距离;可选性

0 引 言

1979年,Erdös 等[1]对2-可选问题作了特征化的论述,并提出猜想：每一个平面图是5-可选的,且存在非4-可选的平面图.十多年以后,此猜想被证实.Voigt[2]成功构造出一个非4-可选的平面图;Thomassen[3]证明了每一个平面图是5-可选的.但是，能否判断出一个给定的平面图是3-或4-可选的问题还未解决.1996年,Gutner[4]证明了这些问题是NP-困难的.因此,研究平面图是3-或4-可选的充分条件变得十分有意义.关于平面图3-可选性的充分条件,总结如下:

定理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].

本文证明了以下结论:

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

1 一些术语和记号

图G是有限、简单、无向图.若平面图G=(V,E)能被嵌入一个平面使得边仅在端点处相交,则称G是可平面的.可平面图在平面内的任何一个具体的使得边仅在端点处相交的嵌入叫平面图.对于平面图G,用V,E,F和δ分别表示平面图G的顶点集、边集、面集和最小度.对任意的一个顶点v∈V,用d(v)表示v在G中的度数,即与v关联的边的条数.分别称度数为k、至少为k或至多为k的顶点为k-点、k+-点和k--点.类似可以定义k-面、k+-面和k--面.若2个圈(或2个面)至少共用一条边,则称这2个圈(或2个面)相邻.连接2个三角形的最短路的长度称为三角形的距离.对于面f∈F,若v1,v2,…,vk是f上按某一时针方向连续出现的点,则记f=[v1,v2,…,vk],且称f为一个(d(v1),d(v2),…,d(vk))-面.一个k-圈是一个长度为k的圈,其大小记为d(f).3-圈又称为三角形.

若一个3-点v关联1个3-面和2个10+-面,则称v是坏点.若一个3-点v关联1个3-面和1个5-面,则称v是半坏点;此时的3-面称为坏面,5-面称为半坏面.若一个3-点v关联2个5-面,则称v是弱点.若一个3-点v关联1个5-面和1个8+-面,则称v是半弱点.否则,其他3-点v都是好点.

2 定理 2 的证明

假设定理2不成立.设G为定理2的一个极小反例,也就是说G是一个极小的非3-可选图.设L是图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)设v是G中的一个3-点,若v同时关联1个3-面和1个5-面,则剩下的1个与之相关联的面是10+-面;

5)设v是G中的一个3-点,若v同时关联2个5-面,则剩下的1个与之相关联的面是8+-面;

6)无弦偶圈至少有1个4+-点.

下面运用权转移方法完成定理2的证明.

权转移规则定义如下:

R1:转给3-点的权.

R1.1:若v是一个好点,则v从3个6+-面各得权 1.

R2:转给 4-点的权.设顶点v关联的面依顺时针排列为 f1,f2,f3,f4.

R2.2:设v是关联三角形的4-点.由引理1中的2)知,v至多关联1个三角形.

R2.3:设v是不关联三角形、但关联5-面的4-点.

现在检验∀x∈V∪F,有ch′(v)≥0.先检验面的最终权.注意到d(f)≠4,7,9.

当d(f)=3时,由权转移规则知,没有权转入和转出,所以ch′(f)=ch(f)=0.

当d(f)=6时,由引理1中的3)知,f不与3-面相邻,且 f不与5-面相邻;由引理1中的6)知,f至少有1个4+-点.因此，由R1.1,R2.1,R2.2.2和R2.3.2知,ch′(f)≥2d(f)-6-6×1=0.

当d(f)=8 时,由引理1中的3)知,f不与3-面相邻.由引理1中的6)知,f至少有一个4+-点.

当d(f)=10时,设 f=[v1v2…v10]是一个10-面.由引理1中的2)和引理1中的6) 知,T(f)≤2,至少有1 个 4+-点;若 T(f)=2,则由对称性,根据3-面的位置可分为2类:

1)v1v2和v6v7各关联1个3-面.根据4+-点所在位置可分为3类:

①当4+-点在坏面上时,由引理1中的3)～5),R1和R2 知,

②当4+-点在半坏面上时,由引理1中的3)～5),R1和R2 知,

2)v1v2和v5v6各关联1个3-面.根据4+-点所在位置可分为3类:

②当4+-点在半坏面上时,由引理1中的3)～5),R1和R2知,

③当4+-点既不在坏面上,也不在半坏面上时,由引理1中的3)～5),R1和R2知,

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

当d(f)=11时,设 f=[v1v2…v11]是一个11-面.由引理1中的2)知,T(f)≤2;当T(f)=2时,由对称性,根据3-面的位置可分为2类:

1)v1v2和v6v7各关联1个3-面.由引理1中的2)～5)和R1知,若v4关联5-面,则

2)v1v2和v5v6各关联1个3-面.由引理1中的2)～5)和R1知,

当T(f)≤1时,由引理1中的2)～5)和R1知,

检验点的最终权.

由引理1中的1)～2)知,d(v)≥3且v至多关联1个三角形.

当d(v)≥6时,由权转移规则知,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.

(责任编辑 陶立方)

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

国家自然科学基金资助项目(11271335)

李晓艳(1990-),女，河南滑县人,硕士研究生.研究方向:运筹学与控制论.

O157.5

A

1001-5051(2016)01-013-05