关于平面图的3-选色

On 3-Choosability of Plane Graphs

图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.