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

On the 3-choosability of Plane Graphs with a Girth of 4 and without 7- and 8- cycles

作　　者：王萃琦[1] 张雪媛[1] WANG cui-qi,ZHANG xue-yuan （China University of Mining and Technology, Xuzhou 221008, China）

机构地区：[1]中国矿业大学,江苏徐州221008

出　　处：《徐州工程学院学报》2007年第2期68-70,共3页Journal of Xuzhou Istitute of Technology

基　　金：中国矿业大学科技基金资助项目（4566）

摘　　要：图G的选色数，记为XL（G），定义为最小的自然数k，使得满足：对任一顶点给定k种颜色的列表，且染色时每个顶点的颜色只能从自身的颜色列表中选择时，总存在图G顶点的一个正常着色．文章证明了每个围长至少为4且不含7-圈和8-圈的平面图是3-可选择的．The choice number of a graph G, denoted by XL（G）, is the minimum number ksuch 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. In this paper, we show that XL（G）≤3 for each plane graph of girth no less than 4 which contains no 7- and 8-cycles.

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

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