围长为4的无7-,8-圈和15-圈平面图的3-选色  

On 3-Choosability of Plane Graphs of Girth No Less Than 4 without 7-,8- and 15-Cycles

作　　者：王萃琦[1] 苗正科[2] 

机构地区：[1]中国矿业大学理学院,江苏徐州221008 [2]徐州师范大学数学系,江苏徐州221008

出　　处：《吉林大学学报（理学版）》2008年第4期658-660,共3页Journal of Jilin University:Science Edition

基　　金：国家自然科学基金(批准号:10471037)

摘　　要：图G的选色数(记为lχ(G)),定义为最小的自然数k,满足当对任一顶点给定k种颜色的列表,且染色时每个顶点的颜色只能从自身的颜色列表中选择时,存在图G顶点的一个正常着色.应用Discharging方法对上述问题进行研究,证明了每个围长至少为4且不含7-圈,8-圈和15-圈的平面图是3-可选择的.The choice number of a graph G, denoted by Xl（G） , is the minimum number k such that if we give lists of k colors to each vertex of G, there is a vertex coloring of G where each vertex receives a color from its own list no matter what the lists are. Now, 3-choosability of plane graphs has become a very active research branch, we have used the discharging method to research the subject, and at last we have shown that each plane graph of girth no less than 4 without 7-,8- and 15-cycles is of 3-choosability.

关 键 词：圈 围长 选色 平面图 欧拉公式 

分 类 号：O157.5[理学—数学]