Premium
A new upper bound on the cyclic chromatic number
Author(s) -
Borodin O. V.,
Broersma H. J.,
Glebov A.,
van den Heuvel J.
Publication year - 2007
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20193
Subject(s) - combinatorics , mathematics , brooks' theorem , list coloring , fractional coloring , chromatic scale , vertex (graph theory) , graph , complete coloring , graph power , edge coloring , upper and lower bounds , planar graph , wheel graph , discrete mathematics , line graph , mathematical analysis
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