Home » Subject » Graph Theory » Coloring » Vertex coloring

Acyclic list colouring of planar graphs.

Importance: High ✭✭✭
Author(s): Borodin, Oleg V.
Fon-Der-Flasss, D. G.
Kostochka, Alexandr V.
Raspaud, André
Sopena, Eric
Subject: Graph Theory
» Coloring
» » Vertex coloring
Keywords:
Recomm. for undergrads: no
Posted by: fhavet
on: March 7th, 2013
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.
add new comment