A new upper bound on the cyclic chromatic number
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