A New Bound on the Cyclic Chromatic Number

In 1969, Ore and Plummer defined an angular coloring as a natural extension of the Four Color Problem: a face coloring of a plane graph where faces meeting even at a vertex must have distinct colors. A natural lower bound is the maximum degree Δ of the graph. Some graphs require ⌊32Δ⌋ colors in an angular coloring. Ore and Plummer gave an upper bound of 2Δ, which was improved to ⌊95Δ⌋ by the authors with Borodin. This article gives a new upper bound of ⌈59Δ⌉ on the angular chromatic number. The cyclic chromatic number is the equivalent dual vertex coloring problem.