没有某些圈的平面图的3可选择性(英文)  

On 3-Choosability of Planar Graphs Without Certain Cycles

作　　者：逄世友[1] 苗连英[1] 曲积斌[1] 苗正科[2] 

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

出　　处：《徐州师范大学学报（自然科学版）》2007年第4期8-10,共3页Journal of Xuzhou Normal University(Natural Science Edition)

基　　金：Research supported by the National Natural Science Foundation of China(10471037)

摘　　要：设G=(V,E)是一个图,对G的每一点v给一颜色集L(v).G称为L列表可染的,如果存在G的点染色f满足:f(u)≠f(v),(u,v)∈E(G),且f(u)∈L(u),u∈V(G).G称为k可选择的,对于任何列表L(v)(这里每一个L(v)恰有k个元素)G都是L列表可染的.本文研究了没有某些圈的平面图的可选择性,证明了没有4,5,7,10圈的平面图是3可选择的.For a graph G= （V,E） ,every vertex v of G is assigned a color set L（v）. G is called L-list colorable if there is a coloring f of vertices of G with f（u） ≠6 f（v）, arbitary （ u, v） ∈ E（G） and f（u） ∈ L（ u）, arbitary u ∈ V（G）. G is called k-choosahle if G is L-list-colorahle for any assignment of lists L（v） where each L（v） has exactly k elements. In this paper, we prove that every planar graph without i-cycles for each i∈{4,5,7,10 } is 3-choosahle.

关 键 词：平面图 圈 可选择性 

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