平面图的无圈5-可选性

Acyclic 5-Choosability of Planar Graph

假设Φ是图G的一个顶点染色。如果任意两个相邻的点染不同颜色,且每个圈至少使用三种颜色,则称Φ是一个无圈染色。如果对于G的任意的k-列表配置L,G有一个无圈L-染色,则称G是无圈k-可选的。本文证明了3圈不与i(i=3,7,9)圈相邻和4圈不与j(3≤j≤6)圈相邻的平面图是无圈5-可选的。

Let Φ is a vertex coloring of graph G. The Φ is acyclic if two adjacent vertices color with different colors and every cycle uses at least three colors. A graph G is k-acyclicallychoosable if G is acyclic L-list colorable for any list assignment L with ▏L(v)▏≥k for each v∈V(G). In this paper, we prove that a planar graph is acyclically 5-choosable if it does not contain an i-cycle adjacent to a j-cycle, where j=3,7,9 if i=3 and 3≤j≤6 if i=4.