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

List improper coloring of graphs of nonnegative characteristic

对每一个顶点υ∈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.