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 ⌊3/2Δ⌋ colors in an angular coloring. Ore and Plummer gave an upper bound of 2Δ, which was improved to ⌊9/5Δ⌋ by the authors with Borodin. This article gives a new upper bound of ⌈5/9Δ⌉ on the angular chromatic number. The cyclic chromatic number is the equivalent dual vertex coloring problem. © 2001 Academic Press.
Journal of Combinatorial Theory. Series B
Number of Pages
Source API URL
Sanders, Daniel P. and Zhao, Yue, "A New Bound On The Cyclic Chromatic Number" (2001). Scopus Export 2000s. 523.