CYCLIC DEGREE AND CYCLIC COLORING OF 3-POLYTOPES

A vertex coloring of a plane graph is called cyclic if th vertices in each face bounding cycle are colored differently. The main result is a n improvement of the upper bound for the cyclic chromatic number of 3- polytopes due to Plummer and Toft, 1987 (J. Graph Theory 11 (1987) 505 -517). The proof is based on a structural property of 3-polytopes, in a sense stronger than that implied by Lebesgue's theorem of 1940. Name ly, precise upper bound is obtained for the minimum cyclic degree of 3 -polytopes with the maximum face size at least 24. (C) 1996 John Wiley & Sons, Inc.