A new upper bound on the cyclic chromatic number
Borodin, O.V. and Broersma, H.J. and Glebov, A. and van den Heuvel, J. (2006) A new upper bound on the cyclic chromatic number. Journal of Graph Theory, 54 (1). pp. 58-72. ISSN 0364-9024
Restricted to UT campus only: Request a copy
|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 . Let be the maximum face degree of a graph. There exist plane graphs with . Ore and Plummer  proved that , which bound was improved to by Borodin, Sanders, and Zhao , and to by Sanders and Zhao .
We introduce a new parameter , which is the maximum number of vertices that two faces of a graph can have in common, and prove that , and if and , then .
Electrical Engineering, Mathematics and Computer Science (EEMCS)
|Link to this item:||http://purl.utwente.nl/publications/63866|
|Export this item as:||BibTeX|
Daily downloads in the past month
Monthly downloads in the past 12 months
Repository Staff Only: item control page
Metis ID: 237816