摘要
图G的选色数记为ch(G),定义为最小的自然数K,使得满足:对于任意顶点给定的K种颜色列表,染色时每个顶点的颜色只能从自身的颜色列表中选择时,图G的顶点总存在一个正常着色。我们证明了每个围长至少为4且不含5-,8-和11-圈的平面图是3-可选色的,以及每个围长至少为4且不含6-,9-和10-圈的平面图是3-可选色的。
The choice number of a graph G, denoted by ch( G), is the minimum number of ksuch that if we give lists ofk colors to each vertex of G, there is a vertex coloring of G where each vertex receives a color from its own list no matter what the lists are. In this paper, we show that ch(G) = 3 for each plane graph of girth no less than 4 which contains no 5 - , 8 - and 11 - cycles and = 3 for each plane graph of girth no less than 4 which contains no 6 - , 9 - and 10 - cycles.
出处
《淮阴工学院学报》
CAS
2007年第5期22-25,共4页
Journal of Huaiyin Institute of Technology
关键词
平面图
3-选色
围长
plane graph
3 - choosability
girth