关于欧拉公式在(3,1)*-列表着色中应用的一个注记  

Note on the use of Euler's formula in(3,1)*-list coloring

作　　者：李红[1] 赵永强[2] 

机构地区：[1]东北大学秦皇岛分校数学与统计学院,河北秦皇岛066004 [2]石家庄学院数学与信息科学系,河北石家庄050035

出　　处：《河北科技大学学报》2012年第4期290-293,304,共5页Journal of Hebei University of Science and Technology

基　　金：National Science Council under Grant(NSC95-2816-M-002-014);河北省教育厅科研资助项目(Z2009140);石家庄学院科研启动基金资助项目(09ZDA003)

摘　　要：如果对于图G的每个满足|L(v)|=k(其中v为G的任意顶点)的列表分配L,G都存在一个L-着色,使得G的每个顶点至多有d个邻居与其自己着有相同的颜色,则称图G是(k,d)*-可选的。在只用欧拉公式和图的结构性质研究2-连通平面图的(3,1)*-列表着色的基础上,研究欧拉公式在平面图的(3,1)*-列表着色中的应用,证明欧拉公式在研究有割点的平面图的(3,1)*-列表着色时也是有效的。A graph G is called （k ,d）＊ -choosable if, for every list assignment L satisfying {L（v）}=k for all v∈ V（G）, there is an L-coloring of G such that each vertex of G has at most d neighbors colored with the same color as itself. Zhao and He first studied the （3,1） ＂ -list coloring of the 2-connected planar graphs just by using Euler＇s formula and the graph＇s structural proper- ties. The paper continues to investigate the use of Euler＇s formula in （3,1）＊ -list coloring the planar graphs, and shows that Euler＇s formula is also practicable in dealing with the planar graphs containing cut vertices.

关 键 词：列表非正常着色 (L d)＊-着色 (m d)＊-可选的 欧拉公式 

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