A new upper bound on the cyclic chromatic number
Oleg Veniaminovich Borodin, Hajo J. Broersma, A. N. Glebov, Jan van den Heuvel · Journal of Graph Theory · 2006
Abstract 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