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.


[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., University of Vermont, Burlington, VT 05401-1455 USA (with thanks to [BFKRS])

December 2003