login/create account
Conjecture Every planar graph is acyclically 5-choosable.
This conjecture would imply to celebrated 5-colour theorems: one due toBorodin [B] stating that every planar graph is acyclically 5-colourable, and one due to Thomassen [T] stating that every plaanar graph is 5-choosable. This two theorems are best possible, because there are planar graphs which are not acyclically 4-colourable and others which are not 4-choosable.
Borodin et al. [BFKRS] showed that every planar graph is acyclically 7-choosable.
Bibliography
[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.
[T] C. Thomassen. Every planar graph is 5-choosable. J. Combin. Theory Ser. B, 62(1994), no. 1, 180–181.
[V] M. Voigt. List colourings of planar graphs. Discrete Math., 120(1993):no. 1-3, 215–219.
* indicates original appearance(s) of problem.
Drupal
CSI of Charles University