A new upper bound on the cyclic chromatic number

O.V. Borodin, Haitze J. Broersma, A. Glebov, J. van den Heuvel

Research output: Contribution to journalArticleAcademicpeer-review

6 Citations (Scopus)


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 $\chi^c$. Let $\Delta^*$ be the maximum face degree of a graph. There exist plane graphs with $\chi^c = \lfloor {3\over 2}\Delta^*\rfloor$. Ore and Plummer [5] proved that $\chi^c \le 2\Delta^*$, which bound was improved to $\lfloor {9\over 5}\Delta^*\rfloor$ by Borodin, Sanders, and Zhao [1], and to $\lceil {5\over 3}\Delta^*\rceil$ 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 $\chi^c \le \max \{\Delta^* + 3k^* + 2,\Delta^* + 14, 3k^* + 6, 18\}$, and if $\Delta^* \ge 4$ and $k^* \ge 4$, then $\chi^c\le \Delta^* + 3k^* + 2$.
Original languageUndefined
Article number10.1002/jgt.20193
Pages (from-to)58-72
Number of pages15
JournalJournal of graph theory
Issue numbersuppl 2/1
Publication statusPublished - 2006


  • EWI-8796
  • METIS-237816
  • IR-63866

Cite this