**Acyclic list-coloring
planar graphs**

A *list-assignment L* gives a list of colors available at each vertex.
Commonly the size *k* of the list is independent on the vertices, and we
talk about a *k-list assignment*. An* L-coloring* assigns each vertex
one of the colors in its list. Usually we want *proper* colorings, so that
adjacent vertices receive distinct colors. The* list-chromatic number *is
the smallest *k* such that every *k*-list assignment *L* has a
proper *L*-coloring. Obviously, the list chromatic number is greater than
or equal to the chromatic number, since the latter is the special case that all
vertices get lists *1,...,k*. Graphs with
list-chromatic number *k* are called *k-choosable*.
It is known that every planar graph is 5-choosable, and that 5 is the best
possible value.

A coloring is *acyclic* if the subgraph induced by the union of any two color classes is a
forest. Borodin [B] proved that every planar graph has an acyclic 5-coloring.
We ask for the list analogue of this result.

**Conjecture: **[BFKRS] *Every planar graph is acyclically
5-choosable.*

Borodin et al. [BFKRS] showed that every planar graph is acyclically 7-choosable. The gap of 2 between the known upper and lower bounds are part of what makes this problem interesting.

**References:**

[B] O.V. Borodin, On acyclic colorings of planar
graphs, *Discrete Math.* **25** (1979) 211-236.

[BFKRS] O.V. Borodin, D.G. Fon-Der Flaass, A.V. Kostochka, A. Raspaud, and E. Sopena, Acyclic
list 7-coloring of planar graphs, *J. of
Graph Theory* **40-2** (2002) 83-90.

Submitted by: Dan Archdeacon, Dept. of Math. and Stat.,

December 2003