Every Toroidal Graph Is Acyclically 8-Choosable  

作　　者：Jian Feng HOU Gui Zhen LIU 

机构地区：[1]Center for Discrete Mathematics,Fuzhou University [2]School of Mathematics,Shandong University

出　　处：《Acta Mathematica Sinica,English Series》2014年第2期343-352,共10页数学学报（英文版）

基　　金：supported by National Natural Science Foundation of China(Grant No.11001055);supported by National Natural Science Foundation of China(Grant No.60672030);Natural Science Foundation of Fujian Province(Grant Nos.2010J05004 and 2011J06001)

摘　　要：A proper coloring of a graphG is acyclic if G contains no 2-colored cycle.A graph G is acyclically L-list colorable if for a given list assignment L={L（v）：v∈V（G）},there exists a proper acyclic coloringφof G such thatφ（v）∈L（v）for all v∈V（G）.If G is acyclically L-list colorable for any list assignment L with｜L（v）｜≥k for all v∈V（G）,then G is acyclically k-choosable.In this article,we prove that every toroidal graph is acyclically 8-choosable.A proper coloring of a graphG is acyclic if G contains no 2-colored cycle.A graph G is acyclically L-list colorable if for a given list assignment L={L（v）：v∈V（G）},there exists a proper acyclic coloringφof G such thatφ（v）∈L（v）for all v∈V（G）.If G is acyclically L-list colorable for any list assignment L with｜L（v）｜≥k for all v∈V（G）,then G is acyclically k-choosable.In this article,we prove that every toroidal graph is acyclically 8-choosable.

关 键 词：Acyclic coloring CHOOSABILITY toroidal graph 

分 类 号：O157.5[理学—数学]