科研之友
微信
新浪微博
Facebook
分享链接
摘要
A proper vertex coloring of a graph G = (V, E) is acyclic if G contains no bicolored cycle. Given a list assignment L = {L(nu) vertical bar nu is an element of V} of G, we say G is acyclically L-list colorable if there exists a proper acyclic coloring pi of G such that pi(nu) is an element of L(nu) for all nu is an element of V. If G is acyclically L-list colorable for any list assignment with |L(nu)| >= k for all nu is an element of V. then G is acyclically k-choosable. In this paper we prove that planar graphs without 4, 7, and 8-cycles are acyclically 4-choosable.
