A proper vertex coloring of a graph G=(V,E) is
acyclic if G contains no bicolored cycle. A graph G is
L-list colorable if for a given list assignment L={L(v): v
Î
V}, there exists a proper coloring c of G such that
c(v)
Î
L(v) for all v
Î
V. If G is L-list colorable for
every list assignment with |L(v)|
³
k for all v
Î
V, then
G is called k-choosable. A graph is said to be acyclically
k-choosable if the obtained coloring is acyclic. In this talk,
we present the links between acyclic k-choosability of G and
Mad(G) defined as the maximum average degree of the subgraphs
of G and give some observations about the relationship between
acyclic coloring, choosability and acyclic choosability.
∼Andre Raspaud教授演講摘要∼