华东师范大学学报(自然科学版) ›› 2016, Vol. 2016 ›› Issue (2): 51-55.doi: 2016.02.007

• 数学 • 上一篇    下一篇

非负特征图的列表不完全染色的研究(英)

许洋   

  1. 青岛农业大学~~理学与信息科学学院, 山东~青岛 266109)
  • 收稿日期:2015-04-01 出版日期:2016-03-25 发布日期:2016-07-25
  • 通讯作者: 许洋,女, 硕士, 讲师, 研究方向为图论及其应用. E-mail:xuyang_825@126.com

List improper coloring of graphs of nonnegative characteristic

 XU  Yang   

  • Received:2015-04-01 Online:2016-03-25 Published:2016-07-25

RichHTML

9

PDF

1021

摘要： 对每一个顶点~$v\in V(G)$, 若任意给定~$k$~种颜色的列表,$G$~都存在一个~$L$-染色,使得~$G$~的每个顶点至多有~$d$~个邻接点与其染相同的颜色,
则称图~$G$~为~$(k,d)^*$-可选的. 设~$G$~为可以嵌入到非负特征曲面的图.本文证明了若图~$G$~为~2-连通的, 且不包含~5-圈、邻接的~3-面和邻接的~4-面时, $G$~是~$(3,1)^*$-可选的.

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

Abstract: A graph G is called (k,d)^*-choosable if, for every list assignment L with |L(v)|=k for all v\in V(G), there is anL$-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

Key words: list improper coloring;characteristic, cycle;Euler's formula

中图分类号: