不含4-圈和7-圈的平面图的列表均匀染色  

Equitable List Coloring of Planar Graphs without 4-and 7-Cycles

作　　者：卜月华[1] 朱俊蕾[1] 

机构地区：[1]浙江师范大学数学系,中国金华321004

出　　处：《湖南师范大学自然科学学报》2007年第4期6-10,共5页Journal of Natural Science of Hunan Normal University

基　　金：国家自然科学基金资助项目(10471131);浙江省自然科学基金资助项目(Y604167)

摘　　要：任意给定图G的一个k-一致列表L,若G是L-可染的,且满足每种颜色至多在「|V(G)|k﹁个点上出现,则称G是k-均匀可选择的.若图G有一个正常k-顶点染色满足任2个色类中的顶点数至多相差1,则称G是k-均匀可染的.应用d ischarge方法,讨论了不含4-圈和7-圈的平面图的结构.证明了对于不含4-圈和7-圈的平面图G,当k≥m ax{Δ(G),8}时,G是k-均匀可选择的,同时,G也是k-均匀可染的.A graph G is equitably k-choosable if, for any k-uniform list assignment L,G is L-colorable and each color appears on at most [｜V（G）｜/k]｜ vertices. A graph G is equitably k-colorable if G has a. proper k-vertex coloring such that the sizes of any two color classes differ by at most 1. It is proved that every plane graph G without 4-and 7-cycles is equitably k-choosable and equitably k-colorable whenever k ≥ max ｜A（G）, 8｜.

关 键 词：均匀染色 列表均匀染色 平面图 圈 

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