A new upper bound on the cyclic chromatic number

A cyclic coloring of a plane graph is a vertex coloring such that vertices incident with the same face have distinct colors. The minimum number of colors in a cyclic coloring of a graph is its cyclic chromatic number χ c . Let Δ * be the maximum face degree of a graph. There exist plane graphs with χ c = ⌊3/2 Δ * ⌋. Ore and Plummer [5] proved that χ c ≤ 2, Δ * , which bound was improved to ⌊9/5, Δ * ⌋ by Borodin, Sanders, and Zhao [1], and to ⌈5/3,Δ * ⌉ by Sanders and Zhao [7]. We introduce a new parameter k * , which is the maximum number of vertices that two faces of a graph can have in common, and prove that χ c ≤ max {Δ * + 3,k * + 2, Δ * + 14, 3, k * + 6, 18}, and if Δ * ≥ 4 and k * ≥ 4, then χ c ≤ Δ * + 3,k * + 2. © 2006 Wiley Periodicals, Inc. J Graph Theory