Centre for Discrete and Applicable Mathematics

 CDAM Research Report, LSE-CDAM-2004-04

April 2004

A New Upper Bound on the Cyclic Chromatic Number

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


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  chic.  Let  Delta*  be the maximum face degree of a graph. There exist plane graphs with   chic = floor(3 Delta*/2).  Ore and Plummer (1969) proved that  chic ≤ 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  chic ≤ max{ Delta* + 3 k* + 2, Delta* + 14, 3 k* + 6, 18 },  and if  Delta* ≥ 4  and  k* ≥ 4, , then  chic ≤ 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, LSE-CDAM-2004-04, 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)-20-7955 7732.
Fax: +44(0)-20-7955 6877.
Email: info@cdam.lse.ac.uk

Introduction to the CDAM Research Report Series.
CDAM Homepage.

Copyright © London School of Economics & Political Science 2005

Last changed: Wed 9 Feb 2005
For comments go to: http://www.maths.lse.ac.uk/webmaster.html