关于平面图的3-选色.pdf

第16卷第5期 淮 阴 工 学 院 学 报 Vol.16No.5 2(X)7年10月 JoumalOfHuaiyinInstituteOfTechno1ogy oct.2007 关于平面图的3一选色 吴桂月，王雪梅 (中国矿业大学理学院，江苏徐州221的8) 摘 要:图G的选色数记为ch(G)，定义为最小的自然数K，使得满足:对于任意顶点给定的K种颜色列表，染色时每个顶 点的颜色只能从自身的颜色列表中选择时，图C的顶点总存在一个正常着色。我们证明了每个围长至少为4且不含5一， 8一和11一圈的平面图是3一可选色的，以及每个围长至少为4且不含6一，9一和10一圈的平面图是3一可选色的。 关健词:平面图;3一选色;围长 中图分类号:0157.5 文献标识码汰 文章编号:1侧为一796l(2(X]7)05一0022一以 0n3一ChoosabilityofPlaneGraPhs WUGui一四e，WANGXue一mei (Colle罗Ofscience，ChinaUnivers ityofMingandTechnolo盯，Xuzhoujiangsu221(X)8，China) A加扮.ct:ThechoicenumberofagraphG，denotedbych(G)，isthe而nimumnumberofksuchthatifwegive lisisofk colorstoeachvertexofG，thereisavertexcoloringOfGwhereeachvertexreceivesaco1or加mitsown listnomatterwhatthelistsare.InthispaPer，we show thatch(G)二3foreachplane脚phofgirthnoless than4whichconiainsnos一，8一andll一c”lesand =3foreachPlane脚phofgirthnolesothan4which containsno6一，9一and10一cycle‘ Keywords:plane乡旧ph;3一choosability;girth 0 引 言 本文所考虑的图都是有限的简单平面图。‘二(V，E，F)表示一个平面图，V，E，F分别为该平面图的 顶点集、边集和面集。若顶点 “是边。的端点，则称u与。相关联。若两个面关和人至少有一条公共边，则 称关和人相邻。一个面了的边界记为b的。N(。)记为，的邻点集，J(，)为点，的度数，显然lN(讨1二 d(刃。‘的最小度和最大度分别记为△(C)和叔C)。度数为k的点称为k一点。若;‘k或1‘k ‘r，此 时k一点分别称为r+一点和;一 点。 对于 ‘中的所有顶点，。V( ‘)的一个颜色安排L(动，使得每个顶点能从其列表中选色并且相邻的 两个顶点不染相同的颜色，称为 ‘的一个L一着色。若对于 ‘的每个满足L二1L(。)IIL(。)1二k，，。 V( )‘}，‘总是存在L一着色，则称 ‘是k一可选色的。使得 ‘是k一可选色的最小的自然数无称为 ‘的 选色数，记为ch()‘。 定义:若一个h一面相关联的所有的顶点3一均为点，则称这个h面为1妙 h‘一面，否则称为是一个 non一lighth一面。若f是一个non一1妙th一面，且b仍 上除一个4一点外，其余均为3一点，则称这个 h一面为mini.alh一面，否则称为non-.in加alh一面。 4一‘面为恰与1个4一面相邻的4一面。 本文证明了无5一，8一和11一圈以及无6一，9一和10一圈的平面图是3一可选色的。 1 引 理 引理1:偶圈是2一可选色的。 收稿日期:2(X刀一08一30