关于无6-,8-和9-圈平面图的3-选色

On 3-Choosability of Plane Graphs without 6-, 8-and 9-Cycles

图G的选色数 ,记为ch(G) ,定义为最小的自然数k ,使得满足 :对任一顶点给定k种颜色的列表 ,且染色时每个顶点的颜色只能从自身的颜色列表中选择时 ,总存在图G顶点的一个正常着色 .文章证明了每个围长至少为 4且不含 6 圈 ,8 圈和 9 圈的平面图是 3

The choice number of a graph G, denoted by ch(G) is the minimum number k such that if we give lists of k 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, it is shown that ch(G)≤3 for each plane graph of girth not less than 4 which contains no 6-, 8-and 9-cycles.