Problem 2.13: List-Coloring Planar Graphs


The first question in Problem 2.13 has been solved. It has been proved that there are 3-colorable planar graphs which are not 4-choosable.

The first such graph was obtained by Margit Voigt of the Technical University in Ilmenau, Germany, in February 1995. She also noticed that such a graph is already contained in the paper of Shai Gutner (referred to in Chapter 2 of "Graph Coloring Problems"), but Gutner seems not to have observed this.

The problem has been dealt with in a paper

M. Voigt and B. Wirth: On 3-colourable non-4-choosable planar graphs, submitted to the Journal of Graph Theory.

It can be obtained on request from Margit Voigt

The same example has been obtained independently by Hammouda Ben Mekki and Henry A. Kierstead (Arizona State University in Tempe, USA). We were informed about this by e-mail in August 1995.

Sept. 8, 1995. Tommy Jensen and Bjarne Toft.


The abovementioned paper has appeared:

M. Voigt and B. Wirth: On 3-colourable non-4-choosable planar graphs, Journal of Graph Theory 24 (1997) 233-235.

Febr. 3, 1998. Tommy Jensen and Bjarne Toft.


Back to Overview menu
Back to Graph Coloring Problems homepage

Last modified February 3, 1998 Tommy Jensen