Centre for Discrete and Applicable Mathematics 

CDAM Research Report, LSECDAM200404April 2004 
O.V. Borodin, H.J. Broersma, A. Glebov, and J. van den Heuvel
Abstract
A cyclic colouring of a plane graph is a vertex colouring such that
vertices incident with the same face have distinct colours. The minimum
number of colours in a cyclic colouring 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} = floor(3 Delta*/2).
Ore and Plummer (1969) proved that
chi^{c} ≤ 2 Delta*, which bound was
improved to floor(9 Delta*/5) by Borodin, Sanders and
Zhao (1999), and to floor(5 Delta*/3) by Sanders and Zhao
(2001).
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} ≤ max{ Delta* + 3 k* + 2,
Delta* + 14, 3 k* + 6, 18 },
and if Delta* ≥ 4 and
k* ≥ 4, , then
chi^{c} ≤ Delta* + 3 k* + 2.
A PDF file (200 kB) with the full contents of this report can be downloaded by clicking here.
Alternatively, if you would like to get a free hard copy of this report, please send the number of this report, LSECDAM200404, together with your name and postal address to:
CDAM Research Reports Series Centre for Discrete and Applicable Mathematics London School of Economics Houghton Street London WC2A 2AE, U.K. 

Phone: +44(0)207955 7732. Fax: +44(0)207955 6877. Email: info@cdam.lse.ac.uk 
Introduction to the CDAM Research Report Series.  
CDAM Homepage. 
Last changed: Wed 9 Feb 2005
For comments go to:
http://www.maths.lse.ac.uk/webmaster.html