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

PDF
Restricted to UT campus only: Request a copy
160Kb

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 $\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$ .
Item Type:	Article
Faculty:	Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:	Discrete Mathematics and Mathematical Programming (DMMP)
Link to this item:	http://purl.utwente.nl/publications/63866
Official URL:	http://dx.doi.org/10.1002/jgt.20193
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Show download statistics for this publication

Repository Staff Only: item control page

Metis ID: 237816