ON S-COLORABLE NON-4-CHOOSABLE PLANAR GRAPHS

An L-list coloring of a graph G is a proper vertex coloring in which e very vertex v gets a color from a list L(v) of allowed colors. G is ca lled k-choosable if all lists L(v) have exactly k elements and if G is L-list colorable for all possible assignments of such lists. Verifyin g conjectures of Erdos, Rubin and Taylor it was shown during the last years that every planar graph is 5-choosable and that there are planar graphs which are not 4-choosable. The question whether there are 3-co lorable planar graphs which are not 4-choosable remained unsolved. The smallest known example far a non-4-choosable planar graph has 75 vert ices and is described by Gutner. In fact, this graph is also 3 colorab le and answers the above question. In addition, we give a list assignm ent for this graph using 5 colors only in all of the lists together su ch that the graph is not List-colorable. (C) 1997 John Wiley & Sons, I nc.