非负特征图的列表不完全染色的研究（英文）  

List improper coloring of graphs of nonnegative characteristic

作　　者：许洋[1] 

机构地区：[1]青岛农业大学理学与信息科学学院,山东青岛266109

出　　处：《华东师范大学学报（自然科学版）》2016年第2期51-55,共5页Journal of East China Normal University(Natural Science)

摘　　要：对每一个顶点υ∈V（G），若任意给定k种颜色的列表，G都存在一个L-染色，使得G的每个顶点至多有d个邻接点与其染相同的颜色，则称图G为（k，d）^＊-可选的．设G为可以嵌入到非负特征曲面的图．本文证明了若图G为2-连通的，且不包含5-圈、邻接的3-面和邻接的4-面时，G是（3，1）^＊-可选的．A graph G is called （k, d）^＊-choosable if, for every list assignment L with ｜L（υ）｜ = k for all υ ∈ V（G）, there is an L-coloring of G such that every vertex has at most d neighbors receiving the same color as itself. Let G be a graph embedded in a surface of nonnegative characteristic. In this paper, we prove that if G is a 2-connected graph, which contains no 5-cycles, adjacent 3-faces and adjacent 4-faces, then G is （3, 1）^＊-choosable.

关 键 词：列表不完全染色 特征 圈 欧拉公式 

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