On a conjecture by Plummer and Toft

The cyclic chromatic number chi(c)(G) of a 2-connected plane graph G is the minimum number of colors in an assigment of colors to the vertices of G su ch that, for every face-bounding cycle f of G, the vertices of f have diffe rent colors. Plummer and Toft proved that, for a 3-connected plane graph G, under the assumption Delta*(G) greater than or equal to 42, where Delta*(G ) is the size of a largest face of G, it holds that chi(c)(G) less than or equal to Delta* (G) + 4. They conjectured that, if G is a 3-connected plane graph, then chi(c)(G) less than or equal to Delta*(G) + 2. In the article the conjecture is proved for Delta*(G) greater than or equal to 24. (C) 199 9 John Wiley & Sons, Inc. J Graph Theory 30: 177-189, 1999.